പ്രതീകങ്ങൾ ആവർത്തിക്കാതെ ഏറ്റവും ദൈർഘ്യമേറിയ സബ്സ്ട്രിംഗ്


വൈഷമ്യ നില മീഡിയം
പതിവായി ചോദിക്കുന്നു അഡോബി അലൈഷൻ ആമസോൺ ആപ്പിൾ ബ്ലൂംബർഗ് ബൈറ്റ്ഡാൻസ് സിസ്കോ ബെ ബൈ ഫേസ്ബുക്ക് ഗോൾഡ്മാൻ സാക്സ് ഗൂഗിൾ മൈക്രോസോഫ്റ്റ് മോർഗൻ സ്റ്റാൻലി ഒറാക്കിൾ എസ്.എ.പി എസ്എപി ലാബുകൾ നീനുവിനും യൂബർ വിഎംവെയർ യാഹൂ
ഹാഷ് ഹാഷിംഗ് സ്ലൈഡിംഗ് വിൻഡോ സ്ട്രിംഗ് രണ്ട് പോയിന്റർ

ഒരു നൽകി സ്ട്രിംഗ്, പ്രതീകങ്ങൾ ആവർത്തിക്കാതെ തന്നെ ഏറ്റവും ദൈർഘ്യമേറിയ സബ്‌സ്ട്രിംഗിന്റെ ദൈർഘ്യം കണ്ടെത്തേണ്ടതുണ്ട്.

കുറച്ച് ഉദാഹരണങ്ങൾ നോക്കാം:

ഉദാഹരണം

pwwkew
3

വിശദീകരണം: ഉത്തരം 3 ദൈർഘ്യമുള്ള “wke” ആണ്

aav
2

വിശദീകരണം: ഉത്തരം നീളം 2 ഉള്ള “av” ആണ്

ഇതിനായുള്ള സമീപനം -1 പ്രതീകങ്ങൾ ആവർത്തിക്കാതെ ഏറ്റവും ദൈർഘ്യമേറിയ സബ്സ്ട്രിംഗ് 

ബ്രൂട്ട് ഫോഴ്സ് 

എല്ലാ സബ്‌സ്ട്രിംഗുകളും പരിശോധിക്കുന്നത് തനിപ്പകർപ്പ് പ്രതീകങ്ങൾക്കായി ഒന്നായിരിക്കണം

  • സമയ സങ്കീർണ്ണത
    • രൂപം കൊള്ളുന്ന സ്ട്രിംഗുകളുടെ എണ്ണം = n * (n + 1) / 2
    • ഓരോ സ്ട്രിംഗും = O (n) പരിശോധിക്കാൻ സമയമെടുക്കുന്നു
    • അങ്ങനെ സമയ സങ്കീർണ്ണത = O (n ^ 3)
  • ബഹിരാകാശ സങ്കീർണ്ണത
    • അദ്വിതീയത പരിശോധിക്കുന്നതിനായി സംഭവിക്കുന്ന പ്രതീകങ്ങളുടെ സംഭരണം = n
    • അങ്ങനെ ബഹിരാകാശ സങ്കീർണ്ണത = O (n)

ഇതിനായുള്ള സമീപനം -2 പ്രതീകങ്ങൾ ആവർത്തിക്കാതെ ഏറ്റവും ദൈർഘ്യമേറിയ സബ്സ്ട്രിംഗ് 

സ്ലൈഡിംഗ് വിൻഡോ 

ഞങ്ങൾ ഇപ്പോൾ അതിന്റെ ട്രാക്ക് സൂക്ഷിക്കുന്നു പരമാവധി നീളമുള്ള സബ്‌സ്ട്രിംഗ് കൂടെ ആവർത്തിക്കുന്ന പ്രതീകങ്ങളൊന്നുമില്ല.

  • മാക്സിമം അനുവദിക്കുക
  • um ദൈർഘ്യം പരമാവധി ഇത് 0 ഉപയോഗിച്ച് സമാരംഭിച്ചു
  • ഞങ്ങൾ അത് ഉറപ്പാക്കുന്നു  i ലേക്ക് j-1 ഇതിനകം പരിശോധിച്ചു
  • ഓരോ തവണയും ഒരു jth പ്രതീകം കണ്ടുമുട്ടുമ്പോൾ
    • S [j] ആവർത്തിച്ചില്ലെങ്കിൽ
      • ഇത് സബ്സ്ട്രിംഗിൽ ചേർക്കാം
      • സബ്സ്ട്രിംഗിന്റെ നീളം കൂട്ടാം
      • j വർദ്ധിപ്പിക്കാം
      • s [j] ഹാഷ്‌സെറ്റിലേക്ക് റെക്കോർഡുചെയ്യാനോ ചേർക്കാനോ കഴിയും
    • S [j] ആവർത്തിച്ചാൽ
      • ഞങ്ങൾ പ്രതീകങ്ങൾ നീക്കംചെയ്യുന്നു
      • ആരംഭ പോയിന്റ് അതായത് ഞാൻ മാറ്റേണ്ടതുണ്ട്
      • സബ്‌സ്ട്രിംഗ് ആവർത്തനരഹിതമാകുന്നതുവരെ ഞങ്ങൾ ഇത് ചെയ്യുന്നു

ജാവ പ്രോഗ്രാം

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

സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത: O (n)

സ്ഥല സങ്കീർണ്ണത: O (k) ഇവിടെ k എന്നത് സ്ലൈഡിംഗ് വിൻഡോയുടെ വലുപ്പമാണ്

ഇതിനായുള്ള സമീപനം -3 പ്രതീകങ്ങൾ ആവർത്തിക്കാതെ ഏറ്റവും ദൈർഘ്യമേറിയ സബ്സ്ട്രിംഗ് 

ഒപ്റ്റിമൈസ് ചെയ്ത സ്ലൈഡിംഗ് വിൻഡോ 

മുകളിലുള്ള സമീപനത്തിൽ, ആവർത്തിച്ചുള്ള പ്രതീകം കാണുന്നത് വരെ ഞങ്ങൾ പ്രതീകങ്ങൾ നീക്കംചെയ്യുകയും സ്ട്രിംഗിന്റെ ആരംഭം മാറ്റുകയും ചെയ്യുന്നു.

ആവർത്തിച്ചുള്ള_ചരണത്തിന്റെ അവസാന സംഭവം നിലനിർത്താൻ ഒരു ഹാഷ്‌മാപ്പ് ഉപയോഗിക്കാം, ഒപ്പം i (സബ്‌സ്ട്രിംഗിന്റെ ആരംഭം) ആ സ്ഥാനത്തേക്ക് നീക്കുകയും അത് O (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

സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത: O (n)

സ്‌പെയ്‌സ് സങ്കീർണ്ണത: O (k) ഇവിടെ k എന്നത് സ്ലൈഡിംഗ് വിൻഡോയുടെ വലുപ്പമാണ്

അവലംബം