Təkrarlanan simvollar olmadan ən uzun alt sətir LeetCode Həlli

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Çiy kərpic Alation Amazon alma Bloomberg ByteDance Cisco DocuSign eBay Expedia Facebook Goldman Sachs google microsoft Morgan Stanley Kahin PayPal SAP SAP Laboratoriyaları XidmətNow Spotify Über VMware Walmart Laboratoriyaları Yahoo Yandex Zillow Zoho
Sükut Hashing Sürüşmə pəncərə Sim İki işarəBaxılıb 52

Təkrarlanan simvollar olmadan ən uzun alt sətir LeetCode Həlli – Verilmiş a sim, simvolları təkrarlamadan ən uzun alt sətrin uzunluğunu tapmaq məcburiyyətindəyik.

Bir neçə misala nəzər salaq:

misal

pwwkew
3

İzahat: Cavab 3 uzunluğu ilə "wke" dir

aav
2

İzahat: Cavab 2 uzunluğunda “av” -dır

Üçün yanaşma-1 Təkrarlanan simvollar olmadan ən uzun alt sətir 

Brute Force 

Bütün alt simlərin təkrarlanan simvollar üçün bir-bir yoxlanılması

  • Zamanın mürəkkəbliyi
    • Yaranacaq simlərin sayı = n * (n + 1) / 2
    • Hər bir simli yoxlamaq üçün vaxt alınır = O (n)
    • Beləliklə zaman mürəkkəbliyi = O (n ^ 3)
  • Kosmik Mürəkkəblik
    • Unikallığı yoxlamaq üçün baş verən simvolların saxlanması = n
    • Beləliklə Kosmik Mürəkkəblik = O (n)

Üçün yanaşma-2 Təkrarlanan simvollar olmadan ən uzun alt sətir 

Sürüşmə pəncərə 

İndi izləyirik maksimum uzunluqlu sətir ilə təkrarlanan simvol yoxdur.

  • Maksimum edək
  • um uzunluq max 0 ilə başlanmışdır
  • Bunu təmin edirik  i üçün j-1 artıq yoxlanılıb
  • Hər dəfə bir jth xarakteri ilə qarşılaşırıq
    • S [j] təkrarlanmazsa
      • Substringə əlavə edilə bilər
      • Substring uzunluğu artırıla bilər
      • j artırıla bilər
      • s [j] qeyd edilə bilər / HashSet-ə əlavə olunur
    • S [j] təkrarlanırsa
      • Simvolları silirik
      • Başlanğıc nöqtəsi yəni dəyişdirilməyim lazımdır
      • Substring təkrar pulsuz olana qədər bunu edirik

Təkrarlanan simvollar olmadan ən uzun alt sətir üçün Java proqramı LeetCode Həlli

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 ++ Proqramı

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

Mürəkkəblik təhlili

Zaman mürəkkəbliyi: O (n)

Kosmik mürəkkəblik: O (k), burada k sürüşən pəncərənin ölçüsüdür

Üçün yanaşma-3 Təkrarlanan simvollar olmadan ən uzun alt sətir 

Optimize edilmiş sürüşmə pəncərə 

Yuxarıdakı yanaşmada təkrarlanan simvolla qarşılaşana qədər simvolları silməyə və simlin başlanğıcını dəyişdirməyə davam edirik.

Hashmap, repeating_character-in son meydana gəlməsini saxlamaq üçün istifadə edilə bilər və i (alt sətrin başlanğıcı) bir O (1) əməliyyatı halına gətirilə bilər.

Java Proqramı

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 ++ Proqramı

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

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi: O (n)

Kosmik mürəkkəblik: O (k), burada k sürüşən pəncərənin ölçüsüdür

References

Translate »
1