קאָנווערט אַ שטריקל וואָס איז יבערכאַזערונג פון אַ סאַבסטרינג פון לענג ק  


שוועריקייט לעוועל מיטל
אָפט געבעטן אין אַקסענטורע אַדאָובי אמעריקאנער עקספּרעסס דאַטאַבריקס פרעעטשאַרגע
האַש האַשינג האַשמאַפּ שטריקל

פּראָבלעם סטאַטעמענט  

אין די "קאָנווערט אַ שטריקל וואָס איז יבערכאַזערונג פון אַ סאַבסטרינג פון לענג ק" פּראָבלעם מיר האָבן געגעבן אַ שטריקל “S” און אַ גאַנץ נומער “k”. שרייב אַ פּראָגראַם צו קאָנטראָלירן צי עס איז מעגלעך צו בייַטן עס צו אַ שטריקל וואָס איז די יבערכאַזערונג פון אַ סאַבסטריישאַן מיט ק אותיות.

ינפּוט פֿאָרמאַט  

דער ערשטער שורה כּולל אַ שטריקל “s”.

די רגע שורה מיט אַ גאַנץ נומער "ק".

רעזולטאַט פֿאָרמאַט  

דרוקן "יאָ" אויב עס איז מעגלעך צו בייַטן עס צו אַ שטריקל וואָס איז די יבערכאַזערונג פון אַ סאַבסטרישאַן מיט ק אותיות. אַנדערש, דרוקן "קיין".

קאַנסטריינץ  

  • 1 <= | ס | <= 10 ^ 6
  • s [i] דאַרף זיין קליין ענגליש אלפאבעט

בייַשפּיל  

abcdefabc
3
YES

דערקלערונג: דאָ מיר קענען פאַרבייַטן "דעף" מיט "אַבק". דערנאָך אונדזער דערהייַנטיקט שטריקל איז "אַבקאַבקאַבק". מיר קענען איצט זען אויב מיר דרייען אַבק דריי מאָל און מיר באַקומען דעם שטריקל.

acdaacda
2
NO

דערקלערונג: עס איז קיין סאַבסטרישאַן פון לענג 2, וואָס קענען מיר ריפּלייסט און געשאפן אַ שטריקל אַזוי אַז מיר באַקומען עס דורך קאַנקאַטאַניישאַן פון די סאַבסטרינג פון לענג k.

אַלגאָריטהם  

1. אַריבער די שטריקל און בויען אַ מאַפּע וואָס כּולל די אָפטקייַט פון סאַבסטרישאַנז (0 צו ק -1, ק צו 2 ק -1, 2 ק צו 3 ק -1 און אַזוי אויף) פון לענג ק. מאַפּס סטרינגס פון לענג k.

2. אויב עס זענען בלויז צוויי פאַרשידענע סאַבסטרישאַנז פון לענג k און די ציילן פון איינער פון די סאַב שטריקל איז 1, דאַן דרוקן "יאָ".

זע אויך
לאָנגעסט סובסטרינג אָן ריפּיטינג אותיות

3. אַנדערש דרוקן "קיין".

ימפּלעמענטאַטיאָן  

C ++ פּראָגראַם צו קאָנווערט אַ שטריקל וואָס איז יבערכאַזערונג פון אַ סובסטרינג פון לענג ק

#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; 
}

Java פּראָגראַם צו קאָנווערט אַ שטריקל וואָס איז יבערכאַזערונג פון אַ סאַבסטרינג פון לענג ק

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

קאַמפּלעקסיטי אַנאַליסיס צו קאָנווערט אַ שטריקל וואָס איז ריפּעטיטיאָן פון אַ סאַבסטרינג פון לענג ק  

צייט קאַמפּלעקסיטי

אָ (N) ווו n איז די גרייס פון דעם געגעבן שטריקל “s”. דאָ מיר סימפּלי פאָרעם סאַבסטריישאַן (0 צו ק -1, ק צו 2 ק -1, 2 ק צו 3 ק -1 און אַזוי אויף) .קי ק לענג און ציילן זייער אָפטקייַט דורך האַש מאַפּע. דאָ מיר טאָן דאָס אין לינעאַר צייט.

ספעיס קאַמפּלעקסיטי

אָ (N) ווו n איז די גרייס פון דעם געגעבן שטריקל “s”. דאָ מיר נוצן האַש מאַפּע פֿאַר סטאָרידזש די ציילן פון די סאַבסטרישאַן פון לענג k.