Ամենաերկար ենթալարը ՝ առանց նիշերի կրկնության


Դժվարության մակարդակ Միջին
Հաճախակի հարցնում են Adobe Ցնծություն Amazon խնձոր Bloomberg ByteDance Cisco eBay Expedia facebook Goldman Sachs-ը Google Microsoft Morgan Stanley Պատգամախոս SAP SAP լաբորատորիաներ Spotify Uber VMware Անտաշ անասուն նողկալի արարած
Խանգարել Հեշինգ Սահող պատուհան String Երկու ցուցիչ

Տրված ա լարային, մենք պետք է գտնենք ամենաերկար ենթալարի երկարությունը ՝ առանց նիշերը կրկնելու:

Եկեք քննենք մի քանի օրինակներ.

Օրինակ

pwwkew
3

Բացատրություն. Պատասխանը «wke» է ՝ 3 երկարությամբ

aav
2

Բացատրություն. Պատասխանը «ավ» է ՝ 2 երկարությամբ

Մոտեցում -1 Ամենաերկար ենթալարը ՝ առանց նիշերի կրկնության 

Ամենակոպիտ բռնությունների կիրառումը 

Ստուգելով բոլոր ենթատողերը մեկը `կրկնօրինակ նիշերի համար

  • Timeամանակի բարդություն
    • Լարերի քանակը, որոնք կստեղծվեն = n * (n + 1) / 2
    • Stամանակ է պահանջվում յուրաքանչյուր տողը ստուգելու համար = O (n)
    • Այսպիսով, ժամանակի բարդությունը = O (n ^ 3)
  • Տիեզերական բարդություն
    • Գոյություն ունեցող նիշերի պահպանում ՝ եզակիությունը ստուգելու համար = n
    • Այսպիսով տիեզերական բարդություն = O (n)

Մոտեցում -2 Ամենաերկար ենթալարը ՝ առանց նիշերի կրկնության 

Սահող պատուհան 

Մենք այժմ հետևում ենք առավելագույն երկարության ենթաշարք հետ առանց կրկնվող նիշերի:

  • Թող առավելագույնը
  • um երկարությունը լինի առավելագույնը ` որը նախաստորագրվում է 0-ով
  • Մենք դա ապահովում ենք  i դեպի j-1 արդեն ստուգված է
  • Ամեն անգամ, երբ մենք հանդիպում ենք jth նիշի
    • Եթե ​​s [j] չի կրկնվում
      • Այն կարող է ավելացվել ենթաշարքին
      • Ենթաշղթայի երկարությունը կարող է ավելացվել
      • j- ը կարող է ավելացվել
      • s [j] - ը կարող է գրանցվել / ավելացվել HashSet- ում
    • Եթե ​​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

Բարդության վերլուծություն

Timeամանակի բարդությունը: Վրա)

Տիեզերական բարդությունO (k) որտեղ k- ը լոգարիթմական պատուհանի չափն է

Մոտեցում -3 Ամենաերկար ենթալարը ՝ առանց նիշերի կրկնության 

Օպտիմիզացված լոգարիթմական պատուհան 

Վերոնշյալ մոտեցման մեջ մենք անընդհատ հեռացնում ենք նիշերը և փոխում ենք տողի սկիզբը, մինչև հանդիպում ենք կրկնվող նիշին:

Հաշման քարտեզը կարող է օգտագործվել ՝ կրկնող_ նիշի վերջին դեպքը պահելու համար, և i- ը (ենթատողի սկիզբը) կարող է տեղափոխվել այդ կետ ՝ այն դարձնելով O (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

Բարդության վերլուծություն

Timeամանակի բարդությունը. O (n)

Տիեզերքի բարդությունը. O (k), որտեղ k- ը լոգարիթմական պատուհանի չափն է

Սայլակ