Last updated on October 10th, 2024 at 12:45 am

Here, We see Longest Substring Without Repeating Characters problem Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc., with different approaches.

List of all LeetCode Solution

Longest Substring Without Repeating Characters LeetCode Solution

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.

1. Longest Substring Without Repeating Characters Leetcode Solution 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;
    }
};

1.1 Explanation

1. Initialize n to the length of the string s and res to 0.
2. Create an unordered map mp to store the last positions of characters.
3. Iterate through the string with index j from 0 to n-1.
4. If s[j] is already in the map and its stored index is greater than 0, update the start index i to max(mp[s[j]], i).
5. Update res to be the maximum of res and the length of the current substring (j – i + 1).
6. Update the map with the current position of s[j].
7. Return res.

1.2 Time Complexity

O(n), where n is the length of the string.

1.3 Space Complexity

O(min(n, m)), where m is the size of the character set.

2. Longest Substring Without Repeating Characters Leetcode Solution 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;
    }
}

2.1 Explanation

1. Initialize n to the length of the string s and ans to 0.
2. Create a map map to store the last positions of characters.
3. Iterate through the string with index j from 0 to n-1.
4. If s.charAt(j) is in the map, update the start index i to max(map.get(s.charAt(j)), i).
5. Update ans to be the maximum of ans and the length of the current substring (j – i + 1).
6. Update the map with the current position of s.charAt(j).
7. Return ans.

2.2 Time Complexity

O(n), where n is the length of the string.

2.3 Space Complexity

O(min(n, m)), where m is the size of the character set.

3. Longest Substring Without Repeating Characters Leetcode Solution 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.1 Explanation

1. Initialize sLen to the length of the string s, maxLen to 0, and maxStr to an empty string.
2. Iterate through the string with index i from 0 to sLen-1.
3. For each character s[i], check if it exists in maxStr.
4. If it does, update maxStr to remove the substring up to and including the first occurrence of s[i].
5. Append s[i] to maxStr.
6. Update maxLen to be the maximum of maxLen and the length of maxStr.
7. Return maxLen.

3.2 Time Complexity

O(n^2), due to the indexOf and substring operations inside the loop.

3.3 Space Complexity

O(n), where n is the length of the string.

4. Longest Substring Without Repeating Characters Leetcode Solution 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.1 Explanation

1. Initialize n to the length of the string s and ans to 0.
2. Create a dictionary mp to store the last positions of characters.
3. Iterate through the string with index j from 0 to n-1.
4. If s[j] is in the dictionary, update the start index i to max(mp[s[j]], i).
5. Update ans to be the maximum of ans and the length of the current substring (j – i + 1).
6. Update the dictionary with the current position of s[j].
7. Return ans.

4.2 Time Complexity

O(n), where n is the length of the string.

4.3 Space Complexity

O(min(n, m)), , where m is the size of the character set.