Каармандарды кайталабастан, эң узун субстринг  


Кыйынчылык деңгээли орто
Көп суралган Adobe Alation Amazon алма Bloomberg ByteDance Cisco Окшош Expedia Facebook Goldman Sachs Гугл Microsoft Морган Стэнли Oracle SAP SAP Labs Spotify Uber VMware Yahoo
таштанды Hashing Жылма терезе аркан Эки көрсөткүч

Берилген а аркан, биз символдорду кайталабастан, эң узун подстринанын узундугун табышыбыз керек.

Бир нече мисалдарды карап көрөлү:

мисал  

pwwkew
3

Түшүндүрүү: Жооп "wke", узундугу 3

aav
2

Түшүндүрмө: Жооп "ав", узундугу 2

Ыкчам-1 үчүн Каармандарды кайталабастан, эң узун субстринг   

Кара күч 

Кайра кайталанган каармандар үчүн баардык подстрицтерди текшерүү

  • Убакыт татаалдыгы
    • Түзүлө турган саптардын саны = n * (n + 1) / 2
    • Ар бир сапты текшерүүгө убакыт кетет = O (n)
    • Ошентип убакыттын татаалдыгы = O (n ^ 3)
  • Космостун татаалдыгы
    • Уникалдуулугун текшерүү үчүн пайда болгон белгилерди сактоо = n
    • Ошентип, Космостун татаалдыгы = O (n)

Ыкчам-2 үчүн Каармандарды кайталабастан, эң узун субстринг   

Жылма терезе 

Азыр биз максималдуу узундук менен кайталануучу белгилер жок.

  • Максимум болсун
  • ум узундук макс ал 0 менен башталат
  • Чейин камсыз кылабыз  i үчүн к-1 мурунтан эле текшерилген
  • Ар бир жолу jth мүнөзүн кезиктиребиз
    • Эгерде s [j] кайталанбаса
      • Аны субстронго кошууга болот
      • Сызыктын узундугун көбөйтсө болот
      • j көбөйтүүгө болот
      • s [j] жаздырып / HashSetке кошсо болот
    • Эгерде s [j] кайталанса
      • Биз белгилерди алып салабыз
      • Баштапкы чекит, башкача айтканда i өзгөртүлүшү керек
      • Биз муну субстринг кайталанганга чейин жасайбыз

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)

ошондой эле
Sort Rotated Array издөө

Космостун татаалдыгы: O (k), мында k - жылма терезенин көлөмү

Ыкчам-3 үчүн Каармандарды кайталабастан, эң узун субстринг   

Оптималдаштырылган Жылма терезе 

Жогорудагы ыкмада, биз кайталанган белгиге жолукканга чейин символдорду алып салып, саптын башын өзгөртө беребиз.

Хэшмапты кайталап_каракеттин акыркы кайталанышын сактоо үчүн колдонсо болот, ал эми I (подстринанын башталышы) О (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

Комплекстик анализ

Убакыттын татаалдыгы: O (n)

Космостун татаалдыгы: O (k), мында k - жылма терезенин көлөмү

шилтемелер