Longest Substring Without Repeating Characters Medium

                                                              LeetCode-Solutions 

1.Longest Substring Without Repeating Characters

Given a string s, find the length of the longest substring without repeating characters.

 

Example 1:

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Example 2:

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Example 4:

Input: s = ""
Output: 0

 

Constraints:

• 0 <= s.length <= 5 * 104
• s consists of English letters, digits, symbols and spaces.

Explanation about the solutions:

To solve this problem we may use  Set data Structure  , Because its unordered collection of an objects in which we cannot store the  duplicate values . So ,Set data structure consists of only unique only if it contains duplicate value then it discards the values from the set .

In this problem ,Whenever we found the repeating character ,we remove the previously added character from the set .

For example we have a set  

                                          {  a b c a b c b }

 

1.To solve this we need two variable i and j and then it is  initialized as int i=0, int j=0 ;

2.We need a variable of Max_count to keep the track of the length as (int Max_count=0;);

3.We need a set data structure 

We move j forward or increment the value for each unique Element .And we increment the value of i , when we found the repeated element , at the any points the difference between the length of i and j is the max point  and its is also known as max length of the substring .

So ,Initially i =0 and j=0 is pointing  to the point  a .So we have no element in the set firstly ,So a  will be added to that set {a} data structure and now increment the value of j=1 and then see the next element and we found that next element is b from the given string " a b c a b c b" ,and b is not a repeating character ,So check weather its present in the set data structure or not so its not present in the set ,So add  that set data structure and now set will become as { a , b} and now we know the length of that max_count is (j-i) .So now the value of i=0 and the j=1 now it will become (1-0=1) and the max_count is now 1 and again increment the value of j and now j value become 2 (j=2) and then check from the  given string and the string is " a b c a b c b " and the element is c and its not present in that set so add that element in the set and increment the  j value ,and the j value become now j=3 . and then check the count of max that is (j-i) and (3-0=3) is the length and the set consists of now {a , b , c } after incrementing the value again check again from the given string  " a b c a b c b" .

Now the element here is  a and here a  is already present in the set {a,b,c } ,So we need to remove the previous element of a from the set and then add that element in the set data structure list and now the set is { b ,c ,a} and now j =4 and and i value is also increment from i=0 to i=1 because we found the repeating character  and now check the value of Max_count  (j - i that is 4-1=3) .Continue in the same manner until the last string 

After doing all these we found the length of the string that is non repeating is  3 ;

So program

Executed code on Ij

package com.company;
import java.util.HashSet;
import java.util.Set;
public class LongestSubstringNonRepeatingCharacter {
    public static void main(String[] args) {
        String s="abcabc";
        int max_count=0;
        int i=0;
        int j=0;
        int strlenght=s.length();
        Set<Character> st=new HashSet<>();
        while (i<strlenght &&j<strlenght){
            if(!st.contains(s.charAt(j)))
            {
                st.add(s.charAt(j));
                j++;
                max_count=Math.max(max_count,j-i);
            }
            else
            {
                st.remove(s.charAt(i));
                i++;
            }
        }
        System.out.println(max_count);
    }
}

 The code i executed in the leetcode :

class Solution {

    public int lengthOfLongestSubstring(String s) {

        int Max_Count=0;

        int i=0;

        int j=0;

      

        Set<Character> st=new HashSet<>();

        while(i<s.length() && j<s.length())

        {

         

            if(!st.contains(s.charAt(j)))

            {

                

                st.add(s.charAt(j));

                j++;

                Max_Count=Math.max(Max_Count,j-i);

            }

            else

            {

                st.remove(s.charAt(i));

                i++;

            }

        }

        return Max_Count;

        

        

    }

}

Execution time