Last updated on July 13th, 2024 at 04:36 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

Topics

Hash Table, Sliding Window, String, Two Pointers

Companies

Adobe, Amazon, Bloomberg, Yelp

Level of Question

Medium

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.