Given a string s, find the length of the longest substring without repeating characters. C++ program. (Explained in detail)

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 * 104
  • s consists of English letters, digits, symbols and spaces.


Code:

class Solution {

public:

    int lengthOfLongestSubstring(string s) {

        int n = s.length();

        unordered_set<char> set;

        int ans = 0, i = 0, j = 0;

        while (i < n && j < n) {

            if (!set.count(s[j])) {

                set.insert(s[j++]);

                ans = max(ans, j - i);

            } else {

                set.erase(s[i++]);

            }

        }

        return ans;

    }

};

Explanation:

  • The solution uses a sliding window technique with two pointers i and j and an unordered_set to store the characters in the current substring.
  • The j pointer moves right until it reaches a repeating character, while the i pointer moves right to shrink the current substring until it no longer contains the repeating character.
  • The length of the current substring is updated by subtracting i from j and storing the maximum value seen so far in the ans variable.
  • After the loop, ans will contain the length of the longest substring without repeating characters.



Comments