අක්ෂර පුනරාවර්තනය නොකර දිගම උපස්ථරය


දුෂ්කරතා මට්ටම මධ්යම
නිතර අසනු ලැබේ ඇෙබෝ ඇලේෂන් ඇමේසන් Apple ජංගම දුරකථන බ්ලූම්බර්ග් ByteDance සිස්කෝ ඊ බේ Expedia ෆේස්බුක් ගෝල්ඩ්මන් සැක්ස් ගූගල් මයික්රොසොෆ්ට් මෝර්ගන් ස්ටැන්ලි ඔරකල් SAP SAP විද්‍යාගාර Spotify Uber VMware යාහූ
හැෂ් හැෂිං ස්ලයිඩින් කවුළුව String පොයින්ටර් දෙකක්

පේළියකි, අක්ෂර පුනරාවර්තනය නොකර දිගම උපස්ථරයේ දිග සොයා ගත යුතුය.

උදාහරණ කිහිපයක් දෙස බලමු:

උදාහරණයක්

pwwkew
3

පැහැදිලි කිරීම: පිළිතුර 3 වන දිග සමඟ “wke” වේ

aav
2

පැහැදිලි කිරීම: පිළිතුර දිග 2 සමඟ “av” වේ

සඳහා ප්‍රවේශය -1 අක්ෂර පුනරාවර්තනය නොකර දිගම උපස්ථරය 

තිරිසන් බලකාය 

සියලුම උපස්ථර පරීක්ෂා කිරීම අනුපිටපත් සඳහා එකක් විය යුතුය

  • කාල සංකීර්ණත්වය
    • සෑදෙන නූල් ගණන = n * (n + 1) / 2
    • එක් එක් නූල් = O (n) පරීක්ෂා කිරීමට කාලය ගතවේ
    • මේ අනුව කාල සංකීර්ණතාව = O (n ^ 3)
  • අභ්‍යවකාශ සංකීර්ණතාව
    • අද්විතීයභාවය පරීක්ෂා කිරීම සඳහා සිදුවන අක්ෂර ගබඩා කිරීම = n
    • මේ අනුව අභ්‍යවකාශ සංකීර්ණතාව = O (n)

සඳහා ප්‍රවේශය -2 අක්ෂර පුනරාවර්තනය නොකර දිගම උපස්ථරය 

ස්ලයිඩින් කවුළුව 

අපි දැන් ඒ ගැන අවධානයෙන් සිටිමු උපරිම දිග උපස්ථරය සමග පුනරාවර්තන අක්ෂර නොමැත.

  • උපරිමයට ඉඩ දෙන්න
  • දිග උපරිම එය 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 (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 යනු ස්ලයිඩින් කවුළුවේ ප්‍රමාණයයි

ආශ්රිත