Leetcode Study Day 15

Longest Substring Without Repeating Characters

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.

My solution

My solution is using the sliding window method. We use two pointers, left and right, to represent the left and right bound of the substring. We move the right pointer to the right until the substring contains a repeating character. Then we move the left pointer to the right and update the maximum length of the substring. We repeat the process until the right pointer reaches the end of the string.

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int left = 0;
        int right = 0;
        int n = s.size();
        int maxCount = INT_MIN;
        string subString = "";

        while (right < n){
            if (subString.find(s[right]) == string::npos){
                subString += s[right];
                right ++;
                maxCount = max(maxCount, int(subString.size()));
            }
            else{
                maxCount = max(maxCount, int(subString.size()));
                left ++;
                right = left;
                subString = "";
            }
            
        }
        return (maxCount == INT_MIN) ? 0 : maxCount;
    }
};

In C++, we can use the find method of the std::string class, if the substring or character I’m looking for is not found, the method will return std::string::npos.