અક્ષરોનું પુનરાવર્તન કર્યા વિના લાંબો સબસ્ટ્રિંગ


મુશ્કેલી સ્તર મધ્યમ
વારંવાર પૂછવામાં આવે છે એડોબ એલેશન એમેઝોન સફરજન બ્લૂમબર્ગ ByteDance સિસ્કો ઇબે એક્સપેડિયા ફેસબુક ગોલ્ડમૅન સૅશ Google માઈક્રોસોફ્ટ મોર્ગન સ્ટેન્લી ઓરેકલ એસએપી એસએપી લેબ્સ Spotify ઉબેર વીએમવેર યાહૂ
હેશ હેશિંગ બારણું વિંડો શબ્દમાળા બે પોઇંટર

આપેલ એ શબ્દમાળા, આપણે અક્ષરોનું પુનરાવર્તન કર્યા વિના લાંબી સબસ્ટ્રિંગની લંબાઈ શોધવી પડશે.

ચાલો થોડા ઉદાહરણો જોઈએ:

ઉદાહરણ

pwwkew
3

સમજૂતી: જવાબ લંબાઈ 3 સાથે "વીક" છે

aav
2

સ્પષ્ટતા: જવાબ લંબાઈ 2 સાથે "એવ" છે

માટે અભિગમ -1 અક્ષરોનું પુનરાવર્તન કર્યા વિના લાંબો સબસ્ટ્રિંગ 

બ્રુટ ફોર્સ 

બધી સબસ્ટ્રિંગ્સ તપાસી રહ્યું છે તે ડુપ્લિકેટ અક્ષરો માટે એક હોવું જોઈએ

  • સમય જટિલતા
    • રચાયેલી તારની સંખ્યા = n * (n + 1) / 2
    • દરેક શબ્દમાળા તપાસવા માટેનો સમય લેવામાં આવે છે = O (n)
    • આમ સમય જટિલતા = O (n ^ 3)
  • અવકાશ જટિલતા
    • વિશિષ્ટતા તપાસવા માટે બનતા પાત્રોનો સંગ્રહ = એન
    • આમ અવકાશ જટિલતા = O (n)

માટે અભિગમ -2 અક્ષરોનું પુનરાવર્તન કર્યા વિના લાંબો સબસ્ટ્રિંગ 

બારણું વિંડો 

અમે હવે ટ્ર trackક રાખીએ છીએ મહત્તમ લંબાઈ સબસ્ટ્રિંગ સાથે કોઈ પુનરાવર્તન પાત્રો.

  • મહત્તમ દો
  • અમ લંબાઈ હોઈ મહત્તમ જેની શરૂઆત 0 સાથે થાય છે
  • અમે તેની ખાતરી કરીએ છીએ  i થી j-1 પહેલેથી જ તપાસ થયેલ છે
  • દર વખતે આપણી સામે જેથ પાત્ર આવે છે
    • જો 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

જટિલતા વિશ્લેષણ

સમયની જટિલતા: ઓ (એન)

જગ્યાની જટિલતા: ઓ (કે) જ્યાં કે સ્લાઇડિંગ વિંડોનું કદ છે

માટે અભિગમ -3 અક્ષરોનું પુનરાવર્તન કર્યા વિના લાંબો સબસ્ટ્રિંગ 

સ્લાઇડિંગ વિંડો timપ્ટિમાઇઝ 

ઉપરોક્ત અભિગમમાં, અમે અક્ષરોને દૂર કરીએ છીએ અને શબ્દમાળાની શરૂઆત બદલાવીએ છીએ ત્યાં સુધી આપણે પુનરાવર્તિત પાત્રને પાર ન કરીએ.

પુનરાવર્તન_ચક્રક્ટરની છેલ્લી ઘટના રાખવા માટે હેશમેપનો ઉપયોગ કરી શકાય છે અને હું (સબસ્ટ્રિંગની શરૂઆત) તેને ઓ (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

જટિલતા વિશ્લેષણ

સમયની જટિલતા: ઓ (એન)

અવકાશ જટિલતા: ઓ (કે) જ્યાં કે સ્લાઇડિંગ વિંડોનું કદ છે

સંદર્ભ