Longest Substring without Repeating Characters

$\mathtt{REFERENCE}$ @ This is a LeetCode Problem.

Problem Description

Given a string. We need to find the sub string of unique characters with longest length.

Examples

Given "abcabcbb", the answer is "abc", which the length is 3.

Given "bbbbb", the answer is "b", with the length of 1.

Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

Solution 1: Brute Force Solution

An obvious solution would be to consider all the substrings and return the maximum length. The implementation is also obvious. From each position of the string, we compute the substring with unique characters. Finally we return the length of maximum size substring.

Complexity

We are computing substring and each of the location. To compute a substring at a location, we might need to traverse the whole string. So the time complexity of this approach will be $O(n^2)$. The space complexity is $O(1)$.

Solution 2: Efficient Solution

This problem can be solved efficiently using two pointers.

1. Set two pointers start = 0 and cursor = 0.
2. Keep increasing cursor until we encounter unique characters.
3. When a duplicate character is encountered
   1. Compute length of the substring of unique characters based upon start and cursor value and update max length.
   2. Move the pointer start towards right until the repeated character is encountered.
4. Repeat steps 2 and 3 until the end.

Implementation

Complexity

By this method, we access each of the characters in the string twice - once by the pointer cursor and other by the pointer start. Hence, the time complexity of this approach is $O(n)$. The space complexity remains O(1). To mark the visited characters we have used a fixed size array.

---

---

---