Самая доўгая падрадок без паўтарэння сімвалаў


Узровень складанасці серада
Часта пытаюцца ў Саман Алацыя амазонка яблык Bloomberg ByteDance Cisco eBay Expedia facebook Goldman Sachs Google Microsoft Morgan Stanley Аракул SAP Лабараторыі SAP Spotify Uber VMware Yahoo
гашыш хэшавання Рассоўнае акно Радок Два паказальнікі

Даецца а радок, мы павінны знайсці даўжыню самай доўгай падрадка, не паўтараючы сімвалы.

Давайце разгледзім некалькі прыкладаў:

Прыклад

pwwkew
3

Тлумачэнне: адказ "wke" даўжынёй 3

aav
2

Тлумачэнне: Адказ даўжынёй 2 "av"

Падыход-1 для Самая доўгая падрадок без паўтарэння сімвалаў 

Грубая сіла 

Праверка ўсіх падрадкоў адзін-адзін на наяўнасць паўтаральных знакаў

  • Складанасць часу
    • Колькасць радкоў, якія будуць сфарміраваны = n * (n + 1) / 2
    • Час патрабуецца праверыць кожны радок = O (n)
    • Такім чынам, складанасць часу = O (n ^ 3)
  • Касмічная складанасць
    • Захоўванне сустракаемых сімвалаў для праверкі унікальнасці = n
    • Такім чынам, складанасць прасторы = O (n)

Падыход-2 для Самая доўгая падрадок без паўтарэння сімвалаў 

Рассоўнае акно 

Цяпер мы адсочваем падрадок максімальнай даўжыні з няма паўтаральных сімвалаў.

  • Няхай максіма
  • даўжыня гм макс які ініцыялізуецца 0
  • Мы гарантуем, што ад  i у J-1 ужо праверана
  • Кожны раз, калі мы сустракаемся з j-м персанажам
    • Калі 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

Аналіз складанасці

Часовая складанасць: O (п)

Касмічная складанасць: 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

Аналіз складанасці

Складанасць часу: O (n)

Складанасць прасторы: O (k), дзе k - памер рассоўнага акна

Спасылкі