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

• First Unique Character in a String
• Valid Parentheses Problem
• How to Evaluate Reverse Polish Notation
• Reverse String in Java
• Longest Common Prefix

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