Skip to main content

Longest Substring Without Repeating Characters (LeetCode)

In this page we will solve the problem Longest Substring Without Repeating Characters from LeetCode.

Problem Statement​

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

Example 1​

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Example 2​

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3​

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Constraints:​

  • 0 <= s.length <= 5 * 10^4
  • s consists of English letters, digits, symbols and spaces.

Solution for Longest Substring Without Repeating Characters​

Intuition and Approach​

We can solve this problem using the sliding window technique. We will use a hash table to store the characters and their indices. We will also use two pointers, left and right, to define the window. The left pointer will point to the start of the window, and the right pointer will point to the end of the window.

We will iterate over the string s using the right pointer. If the character at the right pointer is not in the hash table, we will add it to the hash table with its index. We will then calculate the length of the current window by subtracting the left pointer from the right pointer and update the maximum length if needed.

If the character at the right pointer is already in the hash table, we will move the left pointer to the right of the last occurrence of the character. We will also update the index of the character in the hash table.

We will continue this process until we reach the end of the string s. The maximum length of the substring without repeating characters will be the answer.

Algorithm​

  1. Initialize an empty hash table charIndex to store the characters and their indices.
  2. Initialize the left and right pointers to 0.
  3. Initialize the maxLength variable to store the maximum length of the substring without repeating characters.
  4. Iterate over the string s using the right pointer:
    • If s[right] is not in charIndex, add it to the hash table with its index.
    • Calculate the length of the current window and update the maxLength if needed.
    • If s[right] is already in charIndex, move the left pointer to the right of the last occurrence of s[right].
    • Update the index of s[right] in the hash table.
  5. Continue this process until the end of the string s.
  6. Return the maxLength.

Flowchart​

The flowchart below illustrates the steps involved in the algorithm:

Pseudocode​

function lengthOfLongestSubstring(s: string): number
    let charIndex = new Map()
    let left = 0
    let maxLength = 0

    for right from 0 to s.length - 1
        if s[right] in charIndex
            left = max(left, charIndex[s[right]] + 1)
        charIndex[s[right]] = right
        maxLength = max(maxLength, right - left + 1)

    return maxLength

Implementation and Code​

Here is a live code editor for you to play around with the solution:

Live Editor
function LongestSubstringProblem() {
  const findLongestSubstring = (s) => {
    let charIndexMap = {};
    let left = 0;
    let maxLength = 0;

    for (let right = 0; right < s.length; right++) {
      if (charIndexMap[s[right]] !== undefined) {
        left = Math.max(left, charIndexMap[s[right]] + 1);
      }
      charIndexMap[s[right]] = right;
      maxLength = Math.max(maxLength, right - left + 1);
    }

    return maxLength;
  };

  const testCases = [
    { input: "abcabcbb", expected: 3 },
    { input: "bbbbb", expected: 1 },
    { input: "pwwkew", expected: 3 },
  ];

  return (
    <div>
      {testCases.map((testCase, index) => (
        <div key={index}>
          <p>
            <b>Input:</b> {testCase.input}
          </p>
          <p>
            <b>Output:</b> {findLongestSubstring(testCase.input)}
          </p>
          <p>
            <b>Expected:</b> {testCase.expected}
          </p>
          <hr />
        </div>
      ))}
    </div>
  );
}
Result
Loading...

Code in Different Languages​

Written by @ajay-dhangar
/**
* @param {string} s
* @return {number}
*/
 var lengthOfLongestSubstring = function(s) {
   let charIndexMap = {};
   let left = 0;
   let maxLength = 0;

   for (let right = 0; right < s.length; right++) {
       if (charIndexMap[s[right]] !== undefined) {
           left = Math.max(left, charIndexMap[s[right]] + 1);
       }
       charIndexMap[s[right]] = right;
       maxLength = Math.max(maxLength, right - left + 1);
   }

   return maxLength;

 };

Complexity Analysis​

  • Time Complexity: The time complexity of this solution is O(n)O(n), where n is the length of the input string s. We iterate over the string s once using the right pointer.

  • Space Complexity: The space complexity of this solution is O(min(n,m))O(min(n, m)), where n is the length of the input string s and m is the size of the character set (e.g., 26 for lowercase English letters). We use a hash table to store the characters and their indices, which can have a maximum of m entries.

Test Cases​

We will test the solution with the sample test cases provided in the problem statement.

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Resources​

Authors:

Loading...