Longest substring without repeating characters

Posted by N.K. Chauhan on Mar 31, 2024

Given a string s, the task is to find the length of the longest substring without repeating characters.

Input: s = "cabcabcbb"
Output: 3

Input: s = "aaaaa"
Output: 1

Input: s = "zpwwke"
Output: 3


Solutions

Method 1: In O(n^2) time and O(n) space

This problem can be solved in O(n^2) time and O(n) space with the help of a hash.

The idea is to use two nested loops and check for every substring.

Use a HashSet to identify if the current substring has a repeating character.

Complexity

The time complexity of this solution is O(n^2) and the space complexity is O(n).

Method 2: In O(n) time and O(n) space

This problem can be solved in O(n) time and O(n) space with the help of a sliding window.

The idea is to maintain a sliding window from the ith to the jth index.

Use a HashMap to identify if the current window has a repeating character. This map contains a character as a key and the character's index in the array as a value.

If a repeating character is found at the jth index, look up the index of an already existing duplicate character in the map and move i to the next of this index.

While checking for repeating characters in a map, make sure that the repeating character is in the current window (at >=ith index).

Keep incrementing the jth index until it is less than or equals the last index and the character at the jth index is not repeating.

In each iteration, if the length of the sliding window, i.e., "lengthTillHere," is greater than "lengthSoFar," update lengthSoFar = lengthTillHere.

Complexity

The time complexity of this solution is O(n) and space complexity is O(n).

Related


Program to right rotate an array by 'k' elements

Find maximum and minimum element of an array

Find largest sum contiguous sub-array (Kadane's Algorithm)

Segregate 0s, 1s and 2s in an array (Sort an array of 0s, 1s and 2s)

Move all negative numbers to beginning of the array

Minimize the difference between the heights of smallest and highest tower

Find duplicates in O(n) time and O(1) extra space

Find duplicates in O(n) time and O(n) extra space.

Alternating +ve & -ve in array in O(1) time (maintaining order)

Segregate 0s and 1s in an array (Sort an array of 0s and 1s)

Maximum Product Subarray (Modified Kadane's Algorithm)