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


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

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

זאל ס קוק אין עטלעכע ביישפילן:

בייַשפּיל  

pwwkew
3

דערקלערונג: ענטפער איז "ווקע" מיט לענג 3

aav
2

דערקלערונג: ענטפער איז "אַוו" מיט לענג 2

צוגאַנג -1 פֿאַר לאָנגעסט סובסטרינג אָן ריפּיטינג אותיות   

ברוט פאָרס 

קאָנטראָלירונג אַלע די סאַבסטרישאַנז זייַנען איינער פֿאַר דופּליקאַט אותיות

  • צייט קאַמפּלעקסיטי
    • נומער פון סטרינגס וואָס וועט זיין געגרינדעט = n * (n + 1) / 2
    • צייט איז גענומען צו קאָנטראָלירן יעדער שטריקל = O (n)
    • אזוי צייט קאַמפּלעקסיטי = אָ (n ^ 3)
  • ספעיס קאַמפּלעקסיטי
    • סטאָרידזש פון געשעעניש אותיות פֿאַר קאָנטראָלירונג די אייגנארטיקייט = n
    • אזוי ספעיס קאַמפּלעקסיטי = אָ (n)

צוגאַנג -2 פֿאַר לאָנגעסט סובסטרינג אָן ריפּיטינג אותיות   

סליידינג ווינדאָו 

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

  • זאל דער מאַקסים
  • um לענג זיין מאקס וואָס איז ינישיייטיד מיט 0
  • מיר ענשור אַז פֿון  i צו j -1 איז שוין אָפּגעשטעלט
  • יעדער מאָל מיר טרעפן אַ כאַראַקטער
    • אויב s [j] איז ניט ריפּיטיד
      • עס קענען זיין מוסיף צו די סאַבסטרינג
      • די סאַבסטרינג לענג קענען זיין געוואקסן
      • j קענען זיין ינקראַמענטיד
      • s [j] קענען זיין רעקאָרדעד / צוגעגעבן אין די האַשסעט
    • אויב ס [דזש] איז ריפּיטיד
      • מיר באַזייַטיקן אותיות
      • די סטאַרטינג פונט הייסט איך דאַרפֿן צו זיין טשיינדזשד
      • מיר טאָן דאָס ביז די סאַבסטריישאַן איז פריי יבערכאַזערונג

Java פּראָגראַם

import java.util.*;
class Solution 
{
    public int lengthOfLongestSubstring(String s)
    {
        int max=0;
        HashSet<Character>hash=new HashSet<Character>();
        int i=0;
        int j=0;
        while(i<s.length() && j<s.length())
        {
            if(hash.contains(s.charAt(j)))
            {
                hash.remove(s.charAt(i));
                i=i+1;
            }
            else
            {
             hash.add(s.charAt(j));
             j=j+1;
             max=Math.max(j-i,max);   
            }
        }
        return max;
    }
}

class Main{
  public static void main(String[] args){
    int answer = (new Solution()).lengthOfLongestSubstring("pwwkew");
    System.out.print(answer);
  }
}
pwwkew
3

C ++ פּראָגראַם

class Solution 
{
public:
    int maxs(int a,int b)
    {
        if(a>b)
            return a;
        else
            return b;
    }
public:
    int lengthOfLongestSubstring(string s) 
    {
    int max=0;
    set<char>hash;
    int i=0;
    int j=0;
    while(i<s.length() && j<s.length())
    {
      if(hash.count(s[j]))
      {
                hash.erase(s[i]);
                i=i+1;
      }
      else
     {
     hash.insert(s[j]);
     j=j+1;
     max=maxs(j-i,max);   
     }
    }
    return max;    
    }
};
pwwkew
3

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

צייט קאַמפּלעקסיטי: O (n)

זע אויך
זוך אין סאָרטעד ראָטאַטעד עריי

אָרט קאַמפּלעקסיטי: O (k) ווו ק איז די גרייס פון די סליידינג פֿענצטער

צוגאַנג -3 פֿאַר לאָנגעסט סובסטרינג אָן ריפּיטינג אותיות   

אָפּטימיזעד סליידינג פֿענצטער 

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

א האַשמאַפּ קענען זיין געוויינט צו האַלטן די לעצטע ריפּיטינג_טשאַראַקט און איך (די אָנהייב פון די סאַבסטרינג) קענען זיין אריבערגעפארן צו דעם פונט, אַזוי עס איז אַ אָ (1) אָפּעראַציע.

Java פּראָגראַם

import java.util.*;
class Solution 
{
    public int lengthOfLongestSubstring(String s)
    {
        int max=0;
        HashMap<Character,Integer>hash=new HashMap<Character,Integer>();
        int i=0;
        int j=0;
        while(j<s.length())
        {
            if(hash.containsKey(s.charAt(j)))
            {
                i=Math.max(hash.get(s.charAt(j)),i);
            }
             hash.put(s.charAt(j),j+1);
             max=Math.max(j-i+1,max); 
             j=j+1;
        }
        return max;
    }
}

class Main{
  public static void main(String[] args){
    int answer = (new Solution()).lengthOfLongestSubstring("abcdefg");
    System.out.print(answer);
  }
}
abcdefg
7

C ++ פּראָגראַם

class Solution 
{
public:
    int maxs(int a,int b)
    {
        if(a>b)
            return a;
        else
            return b;
    }
public:
    int lengthOfLongestSubstring(string s) 
    {
    int max=0;
    map<char,int>hash;
    int i=0;
    int j=0;
    while(j<s.length())
    {
    if(hash.count(s[j]))
    {
    i=maxs(hash[s[j]],i);
    }
    hash[s[j]]=j+1;
    max=maxs(j-i+1,max); 
    j=j+1;
    }
    return max;
    }
};
aabbccddee
2

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

צייט קאַמפּלעקסיטי: אָ (n)

אָרט קאַמפּלעקסיטי: אָ (ק) ווו ק איז די גרייס פון די סליידינג פֿענצטער

רעפֿערענצן