Longest Substring Without Repeating Characters Java Program - The Coding Shala

Home >> Interview Questions >> Longest Substring without repeating characters

Longest Substring Without Repeating Characters Java Program

In this post, you will learn how to find the length of the longest substring without repeating characters in a string and its Java solution.

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

Example 1:
Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with a length of 3.

Example 2:
Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with a length of 1.

Example 3:
Input: "pwwkew"
Output: 3

Java Solution of Longest Substring without Repeating Characters

Approach 1:
Using brute force by checking all the substrings. We'll use HashSet to check if characters are unique or not.
Time complexity: O(n^2)
Space Complexity: O(n)
Java Program: 


class Solution {
    public int lengthOfLongestSubstring(String s) {
        int ans = 0;
        int len = s.length();
        for(int i=0; i<len; i++){
            Set<Character> set = new HashSet<Character>();
            set.add(s.charAt(i));
            int tmp = 1;
            for(int j=i+1; j<len; j++){
                char ch = s.charAt(j);
                if(set.contains(ch)) break;
                set.add(ch);
                tmp++;
            }
            if(tmp > ans) ans = tmp;
        }
        return ans;
    }
}

Approach 2:
Using a Sliding Window Algorithm. We will check all the characters in the window if all the characters are unique or not and return the maximum length.
Time Complexity: O(n)
Space Complexity: O(n) - space to store k length char unique.

To Check unique characters we can use HashSet or Hashmap. When we use HashSet it takes O(2n) time and in hashMap, it takes O(n) time.
Java Program(Using HashSet): 

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int len = s.length();
        int i=0,j=0,ans=0;
        Set<Character> set = new HashSet<Character>();
        while(i<len && j<len){
            if(!set.contains(s.charAt(j))){
                set.add(s.charAt(j));
                ans = Math.max(ans, j-i+1);
                j++;
            }else{
                set.remove(s.charAt(i));
                i++;
            }
        }
        return ans;
    }
}

Java program(Using HashMap): 


class Solution {
    public int lengthOfLongestSubstring(String s) {
        int len = s.length();
        int i=0,j=0,ans=0;
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        while(j<len){
            //get max minimum index if unique chars are not there
            if(map.containsKey(s.charAt(j))){
                i = Math.max(i, map.get(s.charAt(j)));
            }
            ans = Math.max(ans, j-i+1); //+1 for if given input has space
            map.put(s.charAt(j), j+1);
            j++;
        }
        return ans;
    }
}

Approach 3:
We can replace an array instead of HashMap in the sliding window problem. we will take an array size 128 for ASCII.
Java Program: 

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int len = s.length();
        int i=0,j=0,ans=0;
        int[] index = new int[128];
        while(j<len){
            i = Math.max(i, index[s.charAt(j)]);
            ans = Math.max(ans, j-i+1);
            index[s.charAt(j)] = j+1;
            j++;
        }
        return ans;
    }
}


Other Posts You May Like
Please leave a comment below if you like this post or found some error, it will help me to improve my content.

Comments

  1. Hi Guys
    I made a simple video explaining the solution using sliding window concept. Please check this out
    https://www.youtube.com/watch?v=XZIzesGjV68&t=115s

    ReplyDelete

Post a Comment

Popular Posts from this Blog

Shell Script to find sum, product and average of given numbers - The Coding Shala

Shell Script to Create a Simple Calculator - The Coding Shala

Richest Customer Wealth LeetCode Solution - The Coding Shala

New Year Chaos Solution - The Coding Shala

Add two numbers in Scala - The Coding Shala