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.
Explanation: The answer is "abc", with a length of 3.
Explanation: The answer is "b", with a length of 1.
Java Solution of Longest Substring without Repeating Characters
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)
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):
Java program(Using HashMap):
We can replace an array instead of HashMap in the sliding window problem. we will take an array size 128 for ASCII.
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