بغير ڪردار کي ورجائڻ جي سڀني کان ڊگهي


تڪليف جي سطح وچولو
بار بار پڇڻ ۾ ايڊوب اليٽنگ Amazon ايپل Bloomberg ByteDance Cisco eBay Expedia ڪريو Goldman سيچ گوگل Microsoft جي مارگن Stanley Oracle SAP ايس اي پي ليبس Spotify سليمان وساڻ VMware ياهو
هاش هاشمي سلائيڊ ونڊو اسٽرنگ ٻه پوتر

ڏنو هڪ جملو، اسان کي اکرن کي ورجائڻ کانسواءِ سڀ کان ڊگهي شي جي ڳولها ڪرڻي پوندي.

اچو ته ڪجھ مثالن ۾ ڏسو.

مثال

pwwkew
3

وضاحت: جواب “وڪي” جي ڊيگهه 3 سان آهي

aav
2

وضاحت: جواب آهي “اي وي” ڊيگهه 2 سان

پهچ -1 لاءِ بغير ڪردار کي ورجائڻ جي سڀني کان ڊگهي 

زبردستي قوت 

تمام ذرا ذرا کي جانچڻ هڪ لاءِ نقل واري اکرن لاءِ هجي

  • وقت جي پيچيدگي
    • اسٽرنگز جو تعداد جيڪي ٺاهيا ويندا = n * (n + 1) / 2
    • هر تار کي جانچڻ لاءِ وقت ورتو وڃي ٿو = اي (ن)
    • ان ڪري وقت جي پيچيدگي = او (n ^ 3)
  • خلائي پيچيدگي
    • انفراديت جي جانچ لاءِ وجود ۾ ايندڙ ڪردارن جو ذخيرو = اين
    • اھڙي طرح خلائي پيچيدگي = اي (ن)

پهچ -2 لاءِ بغير ڪردار کي ورجائڻ جي سڀني کان ڊگهي 

سلائيڊ ونڊو 

اسان هن جو رستو سنڀاليندا آهيون وڌ کان وڌ ڊيگهه سبسٽنگ سان ورجايل ناهي

  • وڌ کان وڌ ڪرڻ ڏيو
  • um ڊگهي ٿي وڃي وڌ جنهن جي شروعات 0 سان ڪئي وئي آهي
  • اسان انهي کي يقيني بڻايون  i جي طرف j- 1 اڳ ئي چيڪ ٿيل آهي
  • اسان جي مقابلي ۾ هر وقت جوڳي ڪردار ملندو آهي
    • جيڪڏهن s [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 لاءِ بغير ڪردار کي ورجائڻ جي سڀني کان ڊگهي 

بهتر سلائيٽنگ دري 

مٿي approachاڻايل طريقي سان ، اسين ڪردار کي هٽائڻ ۽ اسٽرنگ جي شروعات کي تبديل ڪندا رهون ٿا جيستائين اسين بار بار وارو ڪردار نه ڏسندا.

هڪ هشپ استعمال ٿي سگهي ٿو ته آخري واقعا دہرائڻ_ ڪرپيٽرنگ کي ۽ آئون (سب ڊارنگ جي شروعات) کي انهي نقطي تي منتقل ڪري سگهجي ٿو اها او (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

پيچيدگي تجزيي

وقت جي پيچيدگي: اي (ن)

خلائي پيچيدگي: اي (ڪي) جتي ڪ سلائڊنگ ونڊو جي ماپ آهي

حوالا