ಅಕ್ಷರಗಳನ್ನು ಪುನರಾವರ್ತಿಸದೆ ಉದ್ದವಾದ ಸಬ್ಸ್ಟ್ರಿಂಗ್


ತೊಂದರೆ ಮಟ್ಟ ಮಧ್ಯಮ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಅಡೋಬ್ ಅಲೇಷನ್ ಅಮೆಜಾನ್ ಆಪಲ್ ಬ್ಲೂಮ್ಬರ್ಗ್ ಬೈಟ್ ಡೇನ್ಸ್ ಸಿಸ್ಕೋ ಇಬೇ Expedia ಫೇಸ್ಬುಕ್ ಗೋಲ್ಡ್ಮನ್ ಸ್ಯಾಚ್ಸ್ ಗೂಗಲ್ ಮೈಕ್ರೋಸಾಫ್ಟ್ ಮಾರ್ಗನ್ ಸ್ಟಾನ್ಲಿ ಒರಾಕಲ್ ಸ್ಯಾಪ್ ಎಸ್‌ಎಪಿ ಲ್ಯಾಬ್‌ಗಳು Spotify ಉಬರ್ ವರೆ ಯಾಹೂ
ಹ್ಯಾಶ್ ಹ್ಯಾಶಿಂಗ್ ಸ್ಲೈಡಿಂಗ್ ವಿಂಡೋ ಸ್ಟ್ರಿಂಗ್ ಎರಡು ಪಾಯಿಂಟರ್

ನೀಡಲಾಗಿದೆ ಸ್ಟ್ರಿಂಗ್, ಅಕ್ಷರಗಳನ್ನು ಪುನರಾವರ್ತಿಸದೆ ನಾವು ಉದ್ದವಾದ ಸಬ್‌ಸ್ಟ್ರಿಂಗ್‌ನ ಉದ್ದವನ್ನು ಕಂಡುಹಿಡಿಯಬೇಕು.

ಕೆಲವು ಉದಾಹರಣೆಗಳನ್ನು ನೋಡೋಣ:

ಉದಾಹರಣೆ

pwwkew
3

ವಿವರಣೆ: ಉತ್ತರವು ಉದ್ದ 3 ರೊಂದಿಗೆ “wke” ಆಗಿದೆ

aav
2

ವಿವರಣೆ: ಉತ್ತರವು ಉದ್ದ 2 ರೊಂದಿಗೆ “av” ಆಗಿದೆ

ಇದಕ್ಕಾಗಿ ಅಪ್ರೋಚ್ -1 ಅಕ್ಷರಗಳನ್ನು ಪುನರಾವರ್ತಿಸದೆ ಉದ್ದವಾದ ಸಬ್ಸ್ಟ್ರಿಂಗ್ 

ವಿವೇಚನಾರಹಿತ ಪಡೆ 

ಎಲ್ಲಾ ಸಬ್‌ಸ್ಟ್ರಿಂಗ್‌ಗಳನ್ನು ಪರಿಶೀಲಿಸುವುದು ನಕಲಿ ಅಕ್ಷರಗಳಿಗೆ ಒಂದಾಗಿರುತ್ತದೆ

  • ಸಮಯ ಸಂಕೀರ್ಣತೆ
    • ರೂಪುಗೊಳ್ಳುವ ತಂತಿಗಳ ಸಂಖ್ಯೆ = n * (n + 1) / 2
    • ಪ್ರತಿ ಸ್ಟ್ರಿಂಗ್ = ಒ (ಎನ್) ಅನ್ನು ಪರೀಕ್ಷಿಸಲು ಸಮಯ ತೆಗೆದುಕೊಳ್ಳಲಾಗುತ್ತದೆ
    • ಹೀಗಾಗಿ ಸಮಯದ ಸಂಕೀರ್ಣತೆ = O (n ^ 3)
  • ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ
    • ಅನನ್ಯತೆಯನ್ನು ಪರೀಕ್ಷಿಸಲು ಸಂಭವಿಸುವ ಅಕ್ಷರಗಳ ಸಂಗ್ರಹ = 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 ಅಕ್ಷರಗಳನ್ನು ಪುನರಾವರ್ತಿಸದೆ ಉದ್ದವಾದ ಸಬ್ಸ್ಟ್ರಿಂಗ್ 

ಆಪ್ಟಿಮೈಸ್ಡ್ ಸ್ಲೈಡಿಂಗ್ ವಿಂಡೋ 

ಮೇಲಿನ ವಿಧಾನದಲ್ಲಿ, ನಾವು ಪುನರಾವರ್ತಿತ ಅಕ್ಷರವನ್ನು ಕಾಣುವವರೆಗೆ ನಾವು ಅಕ್ಷರಗಳನ್ನು ತೆಗೆದುಹಾಕುತ್ತೇವೆ ಮತ್ತು ಸ್ಟ್ರಿಂಗ್‌ನ ಪ್ರಾರಂಭವನ್ನು ಬದಲಾಯಿಸುತ್ತೇವೆ.

ಪುನರಾವರ್ತಿತ_ಚಾರ್ಟರ್ನ ಕೊನೆಯ ಘಟನೆಯನ್ನು ಉಳಿಸಿಕೊಳ್ಳಲು ಹ್ಯಾಶ್‌ಮ್ಯಾಪ್ ಅನ್ನು ಬಳಸಬಹುದು ಮತ್ತು ನಾನು (ಸಬ್‌ಸ್ಟ್ರಿಂಗ್‌ನ ಪ್ರಾರಂಭ) ಅನ್ನು ಆ ಹಂತಕ್ಕೆ ಸರಿಸಬಹುದು ಮತ್ತು ಇದು ಒ (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

ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

ಸಮಯದ ಸಂಕೀರ್ಣತೆ: ಒ (ಎನ್)

ಸ್ಥಳ ಸಂಕೀರ್ಣತೆ: ಒ (ಕೆ) ಇಲ್ಲಿ ಕೆ ಎಂಬುದು ಸ್ಲೈಡಿಂಗ್ ವಿಂಡೋದ ಗಾತ್ರವಾಗಿದೆ

ಉಲ್ಲೇಖಗಳು