Најдужи подниз без понављања знакова


Ниво тешкоће Средњи
Често питани у адобе Алатион амазонка јабука Блоомберг БитеДанце Цисцо еБаи Екпедиа фацебоок Голдман Сакс гоогле мицрософт Морган Стенли пророчанство САП САП Лабс Спотифи Убер ВМваре иахоо
Хасх Хасхинг Клизни прозор низ Тво Поинтер

С обзиром на а низ, морамо пронаћи дужину најдужег подниза без понављања знакова.

Погледајмо неколико примера:

Пример

pwwkew
3

Објашњење: Одговор је „вке“ дужине 3

aav
2

Објашњење: Одговор је „ав“ дужине 2

Приступ-1 за Најдужи подниз без понављања знакова 

Бруте Форце 

Провера да ли сви поднизови један и један имају дупликате знакова

  • Сложеност времена
    • Број низова који ће се формирати = н * (н + 1) / 2
    • Потребно је време за проверу сваког низа = О (н)
    • Стога је временска сложеност = О (н ^ 3)
  • Сложеност простора
    • Складиштење појавних знакова за проверу јединствености = н
    • Дакле, сложеност простора = О (н)

Приступ-2 за Најдужи подниз без понављања знакова 

Клизни прозор 

Сада пратимо подниз максималне дужине са без понављања знакова.

  • Нека максима
  • ум дужина бити Мак која је иницијализована са 0
  • Осигуравамо да од  i до ј-КСНУМКС је већ проверено
  • Сваки пут кад сретнемо ј-ти лик
    • Ако се с [ј] не понови
      • Може се додати у подниз
      • Дужина подниза се може повећати
      • ј се може повећати
      • с [ј] се може снимити / додати у ХасхСет
    • Ако се с [ј] понови
      • Уклањамо знакове
      • Полазна тачка тј. Треба ме променити
      • То радимо док подниз не постане слободан за понављање

Јава Програм

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

Програм Ц ++

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

Анализа сложености

Временска сложеност: На)

Свемирска сложеност: О (к) где је к величина клизног прозора

Приступ-3 за Најдужи подниз без понављања знакова 

Оптимизирани клизни прозор 

У горе наведеном приступу настављамо уклањати знакове и мењати почетак низа све док не наиђемо на поновљени знак.

Хешмапа се може користити за задржавање последњег појављивања знака репеатинг_цхарацтер и и (почетак подниза) може се преместити до те тачке чинећи то операцијом О (1).

Јава Програм

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

Програм Ц ++

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

Анализа сложености

Сложеност времена: О (н)

Сложеност простора: О (к) где је к величина клизног прозора

Референце