Last updated on January 12th, 2025 at 03:47 am

Here, We see Longest Substring Without Repeating Characters problem Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Hash Table, Sliding Window, String, Two Pointers

Companies

Adobe, Amazon, Bloomberg, Yelp

Level of Question

Medium

Longest Substring Without Repeating Characters LeetCode Solution

1. 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.

2. Coding Pattern Used in Solution

The coding pattern used in the provided code is Sliding Window. This pattern is commonly used to solve problems involving contiguous subarrays or substrings, where the goal is to find the optimal solution by maintaining a “window” that expands or contracts as needed.

3. Code Implementation in Different Languages

3.1 Longest Substring Without Repeating Characters C++

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = int(s.length()), res = 0;
        unordered_map<char, int> mp;

        for (int j = 0, i = 0; j < n; j++){
            if(mp[s[j]] > 0) {
                i = max(mp[s[j]], i);
            }
            res = max(res, j - i + 1);
            mp[s[j]] = j + 1;
        }
        return res;
    }
};

3.2 Longest Substring Without Repeating Characters Java

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length(), ans = 0;
        Map<Character, Integer> map = new HashMap<>();
        for (int j = 0, i = 0; j < n; j++) {
            if (map.containsKey(s.charAt(j))) {
                i = Math.max(map.get(s.charAt(j)), i);
            }
            ans = Math.max(ans, j - i + 1);
            map.put(s.charAt(j), j + 1);
        }
        return ans;
    }
}

3.3 Longest Substring Without Repeating Characters JavaScript

var lengthOfLongestSubstring = function(s) {
  var sLen = s.length,
    maxLen = 0,
    maxStr = '',
    tmpStr,
    posIndex,
    i;

  for( i = 0 ; i < sLen; i++ ){
    tmpStr = s[i];
    posIndex = maxStr.indexOf(tmpStr);

    if(posIndex > -1){
      maxStr = maxStr.substring(posIndex + 1);
    }
    maxStr += tmpStr;
    maxLen = Math.max(maxLen, maxStr.length);
  }
  return maxLen;
};

3.4 Longest Substring Without Repeating Characters Python

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        n = len(s)
        ans = 0
        mp = {}

        i = 0
        for j in range(n):
            if s[j] in mp:
                i = max(mp[s[j]], i)

            ans = max(ans, j - i + 1)
            mp[s[j]] = j + 1

        return ans

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(n)	O(n)
Java	O(n)	O(n)
JavaScript	O(n^2)	O(n)
Python	O(n)	O(n)

• The Sliding Window pattern is used to efficiently solve the problem by maintaining a dynamic window of valid substrings.
• The Java, Python, and C++ implementations are more efficient (O(n) time complexity) compared to the JavaScript implementation (O(n^2) time complexity) due to the use of hash maps instead of indexOf.