Topic describes

Given a string, find the length of the smallest string that does not contain repeating characters.

Example 1:

Input: “abcabcbb” Output: 3 Explanation: Since the oldest string without repeating characters is “ABC”, its length is 3.

Example 2:

Input: “BBBBB” Output: 1 Explanation: Since the oldest string without repeating characters is “b”, its length is 1.

Example 3:

Input: “pwwkew” Output: 3 Explanation: Since the oldest string without repeating characters is “wke”, its length is 3. Note that your answer must be the length of the substring, “pwke” is a subsequence, not a substring.

Solution 1: Sliding Windows

Sliding Windows are an important tool for solving string and array class problems. Locally, we use the following approach:

  1. Assume that the input string is pwwkew
  2. Initialize the map. Key is the character and value is the position of the character in the input string.
  3. Initialize I =0, j=0.
  4. Check whether the element newJValue corresponding to j is in the map:
    1. If it is in a map, remove the element I points to from the map and slide I to the right, continuing with 4.
    2. If it is not in the map, insert it into the map and slide j to the right, continuing with 4. And up the current maximum m.
class Solution { public: int lengthOfLongestSubstring(string str) { int i = 0; int j = 0; int m = 0; int size = (int)str.size(); map<char, int> tmap; while (i<size && j<size) { if (tmap.find(str[j]) == tmap.end()) { tmap.insert(pair<char, int>(str[j], j)); j++; m = max(m, j-i); } else { tmap.erase(tmap.find(str[i])); i++; } } return m; }};Copy the code

Optimize the code

The idea here is that instead of sliding I to the right, you skip to the new repeating element.

For example, for the test case: PWWKEW.

When j=2 and I =0, we already have pw in the map. For j=2, w already has W in the map, so we need to slide I right twice, but we can jump I directly to 2 instead of sliding it step by step. The specific code is as follows:

int lengthOfLongestSubstring(string str) { int i = 0; int j = 0; int m = 0; int size = (int)str.size(); map<char, int> tmap; while (j<size) { if (tmap.find(str[j]) ! = tmap.end()) { i = max(tmap.find(str[j])->second, i); } m = max(m, j-i+1); tmap[str[j]] = j+1; j++; } return m; }Copy the code

learn