کرداروں کو دہرانے کے بغیر سب سے طویل سبسٹریننگ  


مشکل سطح درمیانہ
اکثر پوچھا جاتا ہے ایڈوب اییلیشن ایمیزون ایپل بلومبرگ ByteDance سسکو ای بے Expedia فیس بک گولڈمین سیکس گوگل مائیکروسافٹ مارگن سٹینلی اوریکل SAP SAP لیبز Spotify Uber VMware یاہو
ہیش ہیکنگ سلائیڈنگ ونڈو سلک دو پوائنٹر

دیا ہوا a سٹرنگ، ہمیں حروف کو دہرائے بغیر لمبی لمبی سٹرنگ کی لمبائی تلاش کرنا ہوگی۔

آئیے کچھ مثالوں پر غور کریں:

مثال کے طور پر  

pwwkew
3

وضاحت: جواب "wke" ہے جس کی لمبائی 3 ہے

aav
2

وضاحت: لمبائی 2 کے ساتھ جواب "ایو" ہے

نقطہ نظر -1 کے لئے کرداروں کو دہرانے کے بغیر سب سے طویل سبسٹریننگ   

جانور فورس 

ڈپلیکیٹ حرفوں کے ل all سب سبسٹرنگز کو چیک کرنا

  • وقت کی پیچیدگی
    • تاروں کی تعداد جو تشکیل پائے جائیں گے = n * (n + 1) / 2
    • ہر تار = O (n) کو چیک کرنے کے لئے وقت لیا جاتا ہے
    • اس طرح وقت کی پیچیدگی = O (n ^ 3)
  • خلائی پیچیدگی
    • انفرادیت کی جانچ پڑتال کے ل occur وقوع پذیر حروف کا ذخیرہ = 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 (n)

یہ بھی دیکھتے ہیں
چھانٹی گئی گھماؤ صف میں تلاش کریں

خلائی پیچیدگی: O (K) جہاں k سلائیڈنگ ونڈو کا سائز ہے

نقطہ نظر -3 کے لئے کرداروں کو دہرانے کے بغیر سب سے طویل سبسٹریننگ   

سلائیڈنگ ونڈو کو بہتر بنایا 

مذکورہ بالا نقطہ نظر میں ، ہم حروف کو ہٹاتے اور اسٹرنگ کے آغاز کو تبدیل کرتے رہتے ہیں جب تک کہ ہم بار بار آنے والے کردار کو نہ دیکھیں۔

دہرائے جانے والے_کرٹر کی آخری واردات کو برقرار رکھنے کے لئے ہیش میپ کا استعمال کیا جاسکتا ہے اور میں (اسٹرنگ کی شروعات) کو او (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 سلائیڈنگ ونڈو کا سائز ہے

حوالہ جات