పొడవు K యొక్క సబ్‌స్ట్రింగ్ యొక్క పునరావృతం అయిన స్ట్రింగ్‌ను మార్చండి  


కఠినత స్థాయి మీడియం
తరచుగా అడుగుతుంది యాక్సెంచర్ Adobe అమెరికన్ ఎక్స్ప్రెస్ డేటాబ్రిక్స్ ఫ్రీచార్జ్
హాష్ హ్యాషింగ్ హాష్ మ్యాప్ స్ట్రింగ్

సమస్యల నివేదిక  

“పొడవు K యొక్క సబ్‌స్ట్రింగ్ యొక్క పునరావృతం అయిన స్ట్రింగ్‌ను మార్చండి” సమస్యలో మేము ఒక స్ట్రింగ్ “S” మరియు పూర్ణాంకం “k”. K అక్షరాలతో ఒక సబ్‌స్ట్రింగ్ యొక్క పునరావృతం అయిన స్ట్రింగ్‌కు మార్చడం సాధ్యమేనా అని తనిఖీ చేయడానికి ఒక ప్రోగ్రామ్‌ను వ్రాయండి.

ఇన్‌పుట్ ఫార్మాట్  

“S” స్ట్రింగ్ ఉన్న మొదటి పంక్తి.

“K” అనే పూర్ణాంక విలువ కలిగిన రెండవ పంక్తి.

అవుట్పుట్ ఫార్మాట్  

K అక్షరాలతో ఒక సబ్‌స్ట్రింగ్ యొక్క పునరావృతం అయిన స్ట్రింగ్‌కు మార్చగలిగితే “అవును” అని ముద్రించండి. లేకపోతే, “లేదు” అని ముద్రించండి.

అవరోధాల  

  • 1 <= | లు | <= 10 ^ 6
  • s [i] లోయర్ కేస్ ఇంగ్లీష్ వర్ణమాల అయి ఉండాలి

ఉదాహరణ  

abcdefabc
3
YES

వివరణ: ఇక్కడ మనం “డెఫ్” ను “ఎబిసి” తో భర్తీ చేయవచ్చు. అప్పుడు మా నవీకరించబడిన స్ట్రింగ్ లు “abcabcabc”. ఇప్పుడు, మనం మూడుసార్లు ఎబిసిని కలిపితే సులభంగా చూడవచ్చు, అప్పుడు మనకు ఈ స్ట్రింగ్ వస్తుంది.

acdaacda
2
NO

వివరణ: పొడవు 2 యొక్క సబ్‌స్ట్రింగ్ లేదు, మనం దానిని మార్చవచ్చు మరియు పొడవు k యొక్క సబ్‌స్ట్రింగ్ యొక్క సంగ్రహణ ద్వారా దాన్ని పొందవచ్చు.

అల్గారిథం  

1. స్ట్రింగ్‌లో ప్రయాణించి, పొడవు యొక్క k.maps పొడవు యొక్క సబ్‌స్ట్రింగ్‌ల (0 నుండి k-1, k నుండి 2k-1, 2k నుండి 3k-1 మరియు మొదలైనవి) ఫ్రీక్వెన్సీని కలిగి ఉన్న మ్యాప్‌ను రూపొందించండి.

ఇది కూడ చూడు
అక్షరాలను పునరావృతం చేయకుండా పొడవైన సబ్‌స్ట్రింగ్

2. పొడవు k యొక్క రెండు వేర్వేరు సబ్‌స్ట్రింగ్‌లు మాత్రమే ఉంటే మరియు ఉప స్ట్రింగ్‌లో ఒకటి 1 ఉంటే, “అవును” అని ముద్రించండి.

3. లేకపోతే “NO” అని ప్రింట్ చేయండి.

అమలు  

స్ట్రింగ్‌ను మార్చడానికి సి ++ ప్రోగ్రామ్, ఇది పొడవు K యొక్క సబ్‌స్ట్రింగ్ యొక్క పునరావృతం

#include<bits/stdc++.h> 
using namespace std; 
  
int main() 
{ 
    string s;
    cin>>s;
    int k;
    cin>>k;
    int n=s.length();
    if(n%k!=0)
    {
        cout<<"NO"<<endl;
    }
    else
    {
        unordered_map<string, int> m; 
        for (int i=0; i<n; i+=k) 
        {
            m[s.substr(i, k)]++;
        }
        if(m.size()==1)
        {
            cout<<"YES"<<endl;
        }
        else if(m.size()==2)
        {
            if(m.begin()->second==1 || m.begin()->second==(n/k-1))
            {
                cout<<"YES"<<endl;
            }
            else
            {
                cout<<"NO"<<endl;
            }
        }
        else
        {
            cout<<"NO"<<endl;
        }
    }
    return 0; 
}

స్ట్రింగ్‌ను మార్చడానికి జావా ప్రోగ్రామ్, ఇది పొడవు K యొక్క సబ్‌స్ట్రింగ్ యొక్క పునరావృతం

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

class sum
{ 
  public static void main(String[] args) 
  { 
    Scanner sr = new Scanner(System.in); 
                String s = sr.next();
                int k = sr.nextInt();
                int n=s.length();
                if(n%k!=0)
                {
                    System.out.println("NO");
                }
                else
                {
                    HashMap<String, Integer> m = new HashMap<>();
                    for(int i=0;i<n;i+=k)
                    {
                        String x = s.substring(i,i+k);
                        int temp = m.get(s.substring(i,i+k))==null? 0 : m.get(s.substring(i,i+k));
                        m.put(s.substring(i,i+k), temp+1);
                    }
                    if(m.size()==1)
                    {
                        System.out.println("YES");
                    }
                    else if(m.size()==2)
                    {
                        int flag=0;
                        for(Map.Entry<String, Integer> e : m.entrySet())
                        {
                            if(e.getValue()==1)
                            {
                                flag=1;
                                break;
                            }
                        }
                        if(flag==0)
                        {
                            System.out.println("NO");
                        }
                        else
                        {
                            System.out.println("YES");
                        }
                    }
                    else
                    {
                        System.out.println("NO");
                    }
                }
  } 
} 
abcdabab
YES

ఒక స్ట్రింగ్‌ను మార్చడానికి సంక్లిష్టత విశ్లేషణ, ఇది పొడవు K యొక్క సబ్‌స్ట్రింగ్ యొక్క పునరావృతం  

సమయం సంక్లిష్టత

పై) (ఇక్కడ n ఇచ్చిన స్ట్రింగ్ “s” యొక్క పరిమాణం. ఇక్కడ మనం కేవలం సబ్‌స్ట్రింగ్‌ను (0 నుండి k-1, k నుండి 2k-1, 2k నుండి 3k-1 మరియు మొదలైనవి) సరే k పొడవును ఏర్పరుస్తాము మరియు హాష్ మ్యాప్‌ను ఉపయోగించడం ద్వారా వాటి ఫ్రీక్వెన్సీని లెక్కించండి. ఇక్కడ మేము దీన్ని సరళ సమయంలో చేస్తాము.

అంతరిక్ష సంక్లిష్టత

పై) (ఇక్కడ n ఇచ్చిన స్ట్రింగ్ “s” యొక్క పరిమాణం. ఇక్కడ మనం పొడవు k యొక్క సబ్‌స్ట్రింగ్ యొక్క గణనను నిల్వ చేయడానికి హాష్ మ్యాప్‌ను ఉపయోగిస్తాము.