Самая длинная подстрока без повторяющихся символов


Сложный уровень средний
Часто спрашивают в саман Alation Амазонка Apple Bloomberg ByteDance Cisco eBay Expedia Facebook Goldman Sachs Google Microsoft Morgan Stanley Oracle SAP SAP Labs Spotify Uber VMware Yahoo
Hash хеширования Раздвижное окно строка Два указателя

Учитывая строка, мы должны найти длину самой длинной подстроки без повторяющихся символов.

Давайте рассмотрим несколько примеров:

Пример

pwwkew
3

Пояснение: Ответ «wke» длиной 3

aav
2

Пояснение: Ответ - «av» длиной 2

Подход-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 (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 - размер скользящего окна.

дело