Longest Substring without Repeating Characters

Good day ladies and gentlemen. It is Monday and I am taking this week off from work. I have not taken enough days off so for health reasons I have to take of this week. That said, if I am called to solve and issue I will be available. I am spending the entire week at home.

Today my wife was preparing lunch. She noticed some zucchini in the refrigerator and decided to prepare them stuffed. It is funny that after my wife and I got married, she asked my mother for her recipe on several occasions. The reason is that at my parent’s house, when zucchini were in season they were the first plate for lunch at least once a week. I really liked them the way my Nona and mother prepared them. My mother did not pass on the recipe. Good thing that my wife and I cook. We are on our way to a better recipe. Will let you know when we achieve the goal.

Today I decided to work on LeetCode problem 3 Longest Substring without Repeating Characters.

I will solve the problem using the Java programming language and the VSCode IDE on a Windows 10 computer. Because I will be solving the problem on my computer, I will need to write some test code to collect input, present the argument to the method in question and displaying the results. If you decide to go the simplest route, you should use the on-line IDE provided by LeetCode.

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

Constraints:

o 0 <= s.length <= 5 * 104
o s consists of English letters, digits, symbols and spaces.

Related topics:

o Hash Table
o Two Pointers
o String
o Sliding Window

As you can see the requirements are well stated. If you have questions, take a look at the test cases and the expected results. You should be ready to start developing a solution.

Note that I tend to look at the Related Topics and Hints (none in this case). They tend to give you an idea on how to approach the problem.

abcabcbb
main <<< s ==>abcabcbb<==
main <<<      1234567890...
main <<< output: 3
main <<< output: 3
main <<< output: 3
main <<< output: 3


bbbbb
main <<< s ==>bbbbb<==
main <<<      1234567890...
main <<< output: 1
main <<< output: 1
main <<< output: 1
main <<< output: 1


pwwkew
main <<< s ==>pwwkew<==
main <<<      1234567890...
main <<< output: 3
main <<< output: 3
main <<< output: 3
main <<< output: 3



main <<< s ==><==
main <<<      1234567890...
main <<< output: 0
main <<< output: 0
main <<< output: 0
main <<< output: 0


abcdeafbdgcbb
main <<< s ==>abcdeafbdgcbb<==
main <<<      1234567890...
main <<< output: 7
main <<< output: 7
main <<< output: 7
main <<< output: 7

As I mentioned before, we will need to write a test scaffold. Such code IS NOT PART OF THE SOLUTION.

We are presented with a string of characters. Note that the examples use lower case values. The range is specified in the problem Constraints. The range seems to include 128 characters or half of the ASCII characters.

Our test code seems to read the input string and displayed it. Note that we also display a set of consecutive numbers. They are used to help us track the position of the characters in the string. Note that the first character is labeled with index 1 and not 0. The reason for this will become apparent as we go though the code.

It seems that we have four implementations of the method in question. The first one I did on my own. The other three were generated following the solutions provided by LeetCode. Remember that in order to learn we need to read and experiment. That is exactly how this code and associated post were generated.

The first 4 test cases are provided by LeetCode in the problem definition page. The last test case comes from an animation provided by LeetCode when describing the solutions they propose. My advice is to always check the provided solutions if available. They provide valuable information and techniques we can always use.

class Solution {
    public int lengthOfLongestSubstring(String s) {
        
    }
}

The signature for the method in question is simple. We are provided with a string and need to return the length of the longest string that meets the specified requirements.

    /**
     * Test scaffold
     * @throws IOException
     */
    public static void main(String[] args) throws IOException {
        
        // **** open buffered reader ****
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // **** read input string ****
        String s = br.readLine().trim();

        // **** close buffered reader ****
        br.close();
        
        // ???? ????
        System.out.println("main <<< s ==>" + s + "<==");
        System.out.println("main <<<      1234567890...");

        // **** call method of interest and display result ****
        System.out.println("main <<< output: " + lengthOfLongestSubstring0(s));

        // **** call method of interest and display result ****
        System.out.println("main <<< output: " + lengthOfLongestSubstring1(s));

        // **** call method of interest and display result ****
        System.out.println("main <<< output: " + lengthOfLongestSubstring2(s));

        // **** call method of interest and display result ****
        System.out.println("main <<< output: " + lengthOfLongestSubstring(s));
    }

The test code is simple. We read the input string, display it and call the method in question. Note that we have four implementations.

    /**
     * Given a string s, 
     * find the length of the longest substring without repeating characters.
     * 
     * Runtime: 5 ms, faster than 76.38% of Java online submissions.
     * Memory Usage: 38.8 MB, less than 89.86% of Java online submissions.
     */
    static int lengthOfLongestSubstring0(String s) {
        
        // **** sanity checks ****
        if (s.length() <= 1)
            return s.length();

        // **** initialization ****
        HashMap<Character, Integer> window = new HashMap<>();
        window.put(s.charAt(0), 1);

        int longest = 1;
        int left    = 0;
        int right   = 0;

        // **** traverse string ****
        while (right < s.length() - 1) {

            // **** next character in s (for ease of use) ****
            Character ch = s.charAt(++right);

            // **** add character to window (if not in window) ****
            if (!window.containsKey(ch)) {

                // ???? ????
                // System.out.println("<<< ch: " + ch + " not in window");

                // **** add ch to window ****
                window.put(ch, 1);

                // **** increment longest window size (if needed) ****
                if (window.size() > longest)
                    longest++;
            } 
            
            // **** remove character(s) from window ****
            else {

                // ???? ????
                // System.out.println("<<< ch: " + ch + " already in window");

                // **** remove characters from start until ch is removed ****
                boolean done = false;
                do {

                    // **** remove ch from window ****
                    if (s.charAt(left) == ch) 
                        done = true;
                    else 
                        window.remove(s.charAt(left));

                    // **** increment left ****
                    left++;

                } while (!done);

            }

            // ???? ????
            // System.out.println("<<< sub ==>" + s.substring(left, right + 1) + "<==");
            // System.out.println("<<< left: " + left + " right: " + right + " longest: " + longest);
            // System.out.println("<<< window: " + window.toString());

        }

        // **** return longest window ****
        return longest;
    }

We start by performing a sanity check on the length of the input string.

Following the information providing in the related topics, a sliding window, with two indices and a hash map seem to fall into a nice and simple solution. I always like to come up with the MVP and then optimize as needed including a completely different approach if one is found.

We will traverse the input string from left to right with a variable size sliding window. The characters in the window will be kept in a hash map.

There are two base conditions we need to address on each pass of the loop. The new character on the right may or may not be already in the window. The simple case if it is not. We just add it into the hash map and check and if needed update the size of the longest string. The other condition is when the character is already in the window. In this case we need to shrink the window moving the left boundary right until the original duplicate character has been removed.

That is it. The rest is how well we implement the idea.

BTW all functions / methods contain execution information in the comments section.

   /**
     * Given a string s, 
     * find the length of the longest substring without repeating characters.
     * Slidding window approach.
     * 
     * Runtime: 2 ms, faster than 99.84% of Java online submissions.
     * Memory Usage: 39 MB, less than 70.70% of Java online submissions.
     */
    static int lengthOfLongestSubstring1(String s) {
        
        // **** sanity checks ****
        if (s.length() <= 1)
            return s.length();

        // **** initialization ****
        int[] chars = new int[128];
        int left    = 0;
        int right   = 0;
        int longest = 0;

        // **** traverse the string ****
        while (right < s.length()) {

            // **** get right character ****
            char r = s.charAt(right);

            // ???? ????
            // System.out.println("<<< r: " + r);

            // **** increment character count ****
            chars[r]++;

            // ???? ????
            // System.out.println("<<< chars: " + Arrays.toString(chars));

            // **** remove duplicate character(s) ****
            while (chars[r] > 1) {
                char l = s.charAt(left);
                chars[l]--;
                left++;
            }

            // ???? ????
            // System.out.println("<<< right - left: " + (right - left));

            // **** update longest window ****
            longest = Math.max(longest, right - left + 1);

            // ???? ????
            // System.out.println("<<< sub ==>" + s.substring(left, right + 1) + "<==");
            // System.out.println("<<< longest: " + longest);

            // **** get ready to process next character in s ****
            right++;
        }

        // **** return longest window ****
        return longest;
    }

This is an edited function provided by LeetCode as a possible solution. If interested, please visit the LeetCode website and read the associated description.

    /**
     * Given a string s, 
     * find the length of the longest substring without repeating characters.
     * Sliding window optimized using hashmap.
     * 
     * Runtime: 5 ms, faster than 76.42% of Java online submissions.
     * Memory Usage: 39.3 MB, less than 40.42% of Java online submissions.
     */
    static int lengthOfLongestSubstring2(String s) {
        
        // **** sanity checks ****
        if (s.length() <= 1)
            return s.length();

        // **** initialization ****
        int n       = s.length();
        int longest = 0;
        Map<Character, Integer> map = new HashMap<>();
        
        // **** extend the range between i and j ****
        for (int j = 0, i = 0; j < n; j++) {

            // ???? ????
            // System.out.println("<<< j: " + j + " ch: " + s.charAt(j));

            // **** ****
            if (map.containsKey(s.charAt(j))) {
                i = Math.max(map.get(s.charAt(j)), i);
            }

            // ???? ????
            // System.out.println("<<< i: " + i);

            // **** compute max range between i and j ****
            longest = Math.max(longest, j - i + 1);

            // ???? ????
            // System.out.println("<<< sub ==>" + s.substring(i, j + 1) + "<==");
            // System.out.println("<<< longest: " + longest);

            // **** ****
            map.put(s.charAt(j), j + 1);

            // ???? ????
            // System.out.println("<<< map: " + map.toString());
        }

        // **** return longest window ****
        return longest;
    }

This is a different implementation that has also been edited. The code is from LeetCode. Note that the results are similar to the ones we obtained for our MVP implementation.

    /**
     * Given a string s, 
     * find the length of the longest substring without repeating characters.
     * Sliding window optimized using array.
     * 
     * Runtime: 2 ms, faster than 99.84% of Java online submissions.
     * Memory Usage: 39.2 MB, less than 49.90% of Java online submissions.
     */
    static int lengthOfLongestSubstring(String s) {
        
        // **** sanity checks ****
        if (s.length() <= 1)
            return s.length();

        // **** ****
        Integer[] chars = new Integer[128];

        int left        = 0;
        int right       = 0;
        int longest     = 0;

        // **** ****
        while (right < s.length()) {

            // **** ****
            char r = s.charAt(right);

            // **** ****
            Integer index = chars[r];
            if (index != null && index >= left && index < right)
                left = index + 1;
 
            // **** ****
            longest = Math.max(longest, right - left + 1);

            // **** ****
            chars[r] = right;

            // **** ****
            right++;
        }

        // **** return longest window ****
        return longest;
    }

In this edited solution also provided by LeetCode, the hash map has been replaced with an array. I like to implement solution using available classes to reach to a MVP. From that point on we can edit replacing classes that work fine but do have overhead. We may think that a hash map operated in O(1) to access the value for a key, but that is half the problem. The other is to insert elements in the hash map. In general such operations tend to be somewhat slow when comparing to an array.

Please note that I have left some comments with print statements. I like to watch how algorithms progress. You might want to enable some statements to help you better understand what is going on and perhaps how to get the code to execute in less time.

Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.

If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.

Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer toolset.

Thanks for reading this post, feel free to connect with me John Canessa at LinkedIn.

Regards;

John

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.