LeetCode Java Solution — 3. Longest Substring Without Repeating Characters

We have a string called s , and we need to find the length of the longest substring that has no repeating characters.

What is a string?

A number of characters, including whitespaces and punctuation.

Example:

“This is a string”

What is a substring?

A number of characters that neighbor each other within a string.

Example:

String: “This is a string”

Substring: “is a string”

Not a substring: “astring”

So for this problem, let’s write an input and solve the output in finding the longest substring without repeating characters.

Example:

Input: “kwwpiw”

Output: the answer is 3

Notice that 3 is the output because after sifting through each character, and noticing repeats, we start counting the longest substring from the repeated character again. We find that “wpi” would be the longest substring without repeating characters.

Problem Outline

Next, let’s list a few steps we need to solve this problem:

Step 1) finding the size of the string

Step 2) figure out how to traverse string, two pointer method with a loop

Step 3) figure out the data structure to be used

Step 4) note any constraints

Step 5) draw out the concept

Then, put it all together in a coding language!

Problem Outline Explained

Step 1) To find the size of the string, we call the string s, and use the length method of the String class:

s.length()

Step 2) To figure out how to traverse through each character in the string, we can use a variety of techniques. For this problem, we will go with a two pointer technique.

Step 3) Since we are going with a two pointer technique, we can use a data structure such as a HashMap.

Step 4) Some constraints to consider are empty inputs, so we can say

if (s.length() == 0) 

  return 0;

Step 5) For the coding part, we want to address the constraint of an empty string (usually in the beginning of the function). When coding the loop, we need to move the pointer when we come across a repeated character, input characters using the HashMap data structure, and update the longest substring as we traverse through the string. Then, we end the loop with assigning the longest substring by comparing the length of two substrings. Finally, we return the length of the longest substring.

Code Explained

Header for method:

class Solution {
  static int lengthOfLongestSubstring(String s) {

Empty string constraint:

    if (s.length() == 0)
      return 0;

Declaring HashMap key value pair of character and integer, and maximum substring variable:

    HashMap<Character, Integer> map = new HashMap<Character, Integer>();
    int max_substring = 0;

Loop header with i and j as the pointers:

     for (int i = 0, j = 0; i < s.length(); i++){

When there is a repeat character found, assign j pointer to that character:

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

Continue to keep track of characters with key value pairs by putting them into HashMap:

        map.put(s.charAt(i), i);

Update max substring variable by comparing the max substring and the characters traversed:

        max_substring = Math.max(max_substring, i — j + 1);

      }

Return the max substring variable:

       return max_substring;
    }
}

Full code:

class Solution {
  static int lengthOfLongestSubstring(String s) {
    if (s.length() == 0)
      return 0;

    HashMap<Character, Integer> map = new HashMap<Character, Integer>();
    int max_substring = 0;

    for (int i = 0, j = 0; i < s.length(); i++){
      if (map.containsKey(s.charAt(i))){
        j = Math.max(j, map.get(s.charAt(i)) + 1);
      }

      map.put(s.charAt(i), i);

      max_substring = Math.max(max_substring, i — j + 1);
     
     }
     return max_substring;
    }
}

Credit goes to the problem solver cbmbbz on LeetCode and their solution. They provided a great solution to this problem that I find is straightforward to understand.

Thanks for reading!