Longest Unique Substring

Posted: 17 Jul, 2020
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

Given a string input of length n, find the length of the longest substring without repeating characters i.e return a substring that does not have any repeating characters.

Substring is the continuous sub-part of the string formed by removing zero or more characters from both ends.

Input format:
 The first and the only line consists of a string of length n containing lowercase alphabets.
Output format:
 You need to print the length of the longest unique characters substring.
Constraints:
 1<= n <=10^5

Time Limit: 1 sec
Approach 1
  • Create all the substrings of the string.
  • For every substring, check if it consists of unique characters.
  • To check if the substring has duplicate characters, we will use a HashSet. We will iterate through all the characters in the string and put them into the set one by one. Before putting one character, we check if the set already contains it. If it does, the substring doesn't contain unique characters and we can break the loop at that point. If the entire loop is executed without breaking, then the substring contains unique characters
  • If the length of the current substring with unique characters is greater than the maximum length of the substring we've found (initially 0), then we'll update it.
  • Return the maximum length of the substring with unique characters
Try Problem