वर्णहरू दोहोर्याई बिना सब भन्दा लामो सबस्ट्रि।


कठिनाई तह मध्यम
बारम्बार सोधिन्छ एडोब एलेसन अमेजन एप्पल ब्लूमबर्ग बाइटडेन्स सिस्को eBay Expedia फेसबुक Goldman सैक्स गुगल माइक्रोसफ्ट मोर्गन स्टेनले बजेट SAP SAP ल्याबहरू Spotify Uber VMware याहू
हैश ह्याशिंग स्लाइडि Wind विन्डो घागो दुई पोइन्टर

दिइएको string, हामीले वर्णहरू दोहोर्याउँनु भन्दा लामो सबस्ट्रि ofको लम्बाइ पत्ता लगाउनु पर्छ।

केही उदाहरणहरू हेरौं:

उदाहरणका

pwwkew
3

स्पष्टीकरण: उत्तर "wke" लम्बाई with को साथ छ

aav
2

स्पष्टीकरण: लम्बाई २ को साथ उत्तर "av" हो

दृष्टिकोण -१ को लागि वर्णहरू दोहोर्याई बिना सब भन्दा लामो सबस्ट्रि। 

ब्रुट फोर्स 

सबै सबस्ट्रिंगहरू जाँच गर्दैछ एक नक्कल क्यारेक्टरहरूको लागि

  • समय जटिलता
    • तारहरूको संख्या जुन गठन हुन्छ = n * (n + १) / २
    • समय प्रत्येक स्ट्रि check = O (n) जाँच गर्न लिइन्छ
    • यस प्रकार समय जटिलता = O (n ^ 3)
  • ठाउँ जटिलता
    • विशिष्टता जाँच गर्नका लागि भइरहेको वर्णहरूको भण्डारण = n
    • यसैले स्पेस जटिलता = O (n)

दृष्टिकोण -१ को लागि वर्णहरू दोहोर्याई बिना सब भन्दा लामो सबस्ट्रि। 

स्लाइडि Wind विन्डो 

हामी अब ट्रयाक राख्छौं अधिकतम लम्बाई स्ट्रस्ट्रिंग संग कुनै दोहोरिने वर्णहरू छैनन्।

  • म्याक्सिम गरौं
  • उम लम्बाई अधिकतम जुन ० बाट आरम्भ गरिएको छ
  • हामी सुनिश्चित गर्दछौं कि बाट  i लाई जे 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

C ++ कार्यक्रम

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 स्लाइडिंग विन्डोको आकार हो

दृष्टिकोण -१ को लागि वर्णहरू दोहोर्याई बिना सब भन्दा लामो सबस्ट्रि। 

अनुकूलित स्लाइडिंग विन्डो 

माथिको दृष्टिकोणमा, हामी क्यारेक्टरहरू हटाउँदै स्ट्रिंगको सुरू परिवर्तन गर्दै छौं जबसम्म हामी दोहोरिएको वर्ण भेट्दैनौं।

दोहोर्याउने_अनुरोधकको अन्तिम घटना राख्नका लागि ह्यासम्याप प्रयोग गर्न सकिन्छ र i (सबस्ट्रिंगको सुरूवात) लाई ओ (१) अपरेशन बनाएर त्यस बिन्दुमा सार्न सकिन्छ।

जावा कार्यक्रम

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 ++ कार्यक्रम

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 स्लाइडिंग विन्डोको आकार हो

सन्दर्भ