Coding Challenge: Longest Substring Without Repeating Characters

Mon, Apr 8, 2019

Difficulty: Easy

Problem

Given a string, find the length of the longest substring without repeating characters.

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.

Analysis

Note: In the 3rd example, another possible solution is also kew.

A possible approach to solve this problem is to separate the string into substring groups. We can start with a big group (length - 1) so that we might find the answer earlier.

For example, using the 3rd example given, we can split the string initially like this:

['pwwkew', 'w']

At the beginning, the right part of the split will be smaller than the left one. But with each iteration, the left part will become smaller and the right part will become bigger until they are of equal size.

Here's an example of how that looks:

['pwwkew', 'w']  # 1st iteration
['pwwk', 'ew']  # 2nd iteration
['pww', 'kew']  # 3rd iteration, answer: 'kew'
['pw', 'wk', 'ew']  # 4th iteration (not reached)
['p', 'w', 'w', 'k', 'e', 'w']  # 5th iteration (not reached)

Then on each group, we simply need to check if it contains unique characters.

Solution (Python)

Here is my solution using Python 3:

def longest_substring(s: str) -> int:
    """
    Returns the length of the longest substring with unique
    chracters in a string 's'.
    """
    n = len(s) - 1
    while n > 0:
        # Split the string into groups of size n
        groups = [s[i:i+n] for i in range(0, len(s), n)]

        for g in groups:
            # Ignore the small substring groups
            if len(g) == n:
                # Check if they have unique characters
                # using a set
                if len(set(g)) == len(g):
                    return len(g)

        n -= 1

Takeaways

A very common task also present in other coding challenges is creating substring groups of size n from a string, as shown in this challenge. In Python we can do this in one line, although I feel it's a bit hard to remember it:

groups = [s[i:i+n] for i in range(0, len(s), n)]

Another very simple concept is the checking of unique characters in a string. To achieve this we simply conver the string to a set, which will remove all the duplicate characters, and then compare its length to the original string's length. No need to loop through the string:

unique = len(set(g)) == len(g)

References

Stack Overflow: Split string every nth character?

codingchallenges