### 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

Hi Guys

ReplyDeleteI made a simple video explaining the solution using sliding window concept. Please check this out

https://www.youtube.com/watch?v=XZIzesGjV68&t=115s