Longest substring without repeating characters

Posted by N.K. Chauhan on Feb 06, 2023

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


Print all Subsets (Power Set) of a given array

Program to print Union of two sorted arrays

Two Sum - return index of a pair of array elements with a given sum

Merge two sorted arrays in O(1) space

Word Break Problem (Using HashMap and DP)

Find a triplet in an array that sums to a given number

Program to print Intersection of two sorted arrays

Rain water trapping problem - O(n) time & O(n) space

Print all possible permutations of an Array in O(1) space

Count the number of inversions in an array - in O(n log n) time