Question

1100. Find K-Length Substrings With No Repeated Characters

中文文档

Description

Given a string s and an integer k, return _the number of substrings in _s_ of length _k_ with no repeated characters_.

 

Example 1:

Input: s = "havefunonleetcode", k = 5
Output: 6
Explanation: There are 6 substrings they are: 'havef','avefu','vefun','efuno','etcod','tcode'.

Example 2:

Input: s = "home", k = 5
Output: 0
Explanation: Notice k can be larger than the length of s. In this case, it is not possible to find any substring.

 

Constraints:

• 1 <= s.length <= 104
• s consists of lowercase English letters.
• 1 <= k <= 104

Solutions

Solution 1: Two Pointers + Counter

We observe that all characters are lowercase letters, so there are at most $26$ different characters. Therefore, if $k > 26$ or $k > n$, it is impossible to find any substring of length $k$ without repeated characters, and we can directly return $0$.

Next, we use two pointers $j$ and $i$ to maintain a sliding window, where $j$ is the left endpoint of the sliding window, $i$ is the right endpoint of the sliding window, and a counter $cnt$ is used to count the number of occurrences of each character in the sliding window.

We traverse the string $s$, each time adding $s[i]$ to the sliding window, i.e., $cnt[s[i]]++$. If at this time $cnt[s[i]] > 1$ or $i - j + 1 > k$, then we loop to remove $s[j]$ from the sliding window, i.e., $cnt[s[j]]--$, and move $j$ to the right. If after moving $j$ to the right, the window size $i - j + 1$ is exactly equal to $k$, it means that the string in the sliding window is a substring that meets the requirements of the problem, and we increment the result by one.

After the traversal ends, we can get the number of all substrings that meet the requirements of the problem.

The time complexity is $O(n)$, and the space complexity is $O(C)$. Here, $n$ is the length of the string $s$, and $C$ is the size of the character set. In this problem, $C = 26$.

class Solution:
  def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:
    n = len(s)
    if k > n or k > 26:
      return 0
    ans = j = 0
    cnt = Counter()
    for i, c in enumerate(s):
      cnt[c] += 1
      while cnt[c] > 1 or i - j + 1 > k:
        cnt[s[j]] -= 1
        j += 1
      ans += i - j + 1 == k
    return ans

class Solution {
  public int numKLenSubstrNoRepeats(String s, int k) {
    int n = s.length();
    if (k > n || k > 26) {
      return 0;
    }
    int[] cnt = new int[128];
    int ans = 0;
    for (int i = 0, j = 0; i < n; ++i) {
      ++cnt[s.charAt(i)];
      while (cnt[s.charAt(i)] > 1 || i - j + 1 > k) {
        cnt[s.charAt(j++)]--;
      }
      ans += i - j + 1 == k ? 1 : 0;
    }
    return ans;
  }
}

class Solution {
public:
  int numKLenSubstrNoRepeats(string s, int k) {
    int n = s.size();
    if (k > n || k > 26) {
      return 0;
    }
    int cnt[128]{};
    int ans = 0;
    for (int i = 0, j = 0; i < n; ++i) {
      ++cnt[s[i]];
      while (cnt[s[i]] > 1 || i - j + 1 > k) {
        --cnt[s[j++]];
      }
      ans += i - j + 1 == k;
    }
    return ans;
  }
};

func numKLenSubstrNoRepeats(s string, k int) (ans int) {
  if k > len(s) || k > 26 {
    return 0
  }
  cnt := [128]int{}
  for i, j := 0, 0; i < len(s); i++ {
    cnt[s[i]]++
    for cnt[s[i]] > 1 || i-j+1 > k {
      cnt[s[j]]--
      j++
    }
    if i-j+1 == k {
      ans++
    }
  }
  return
}

function numKLenSubstrNoRepeats(s: string, k: number): number {
  const n = s.length;
  if (k > n) {
    return 0;
  }
  const cnt: Map<string, number> = new Map();
  for (let i = 0; i < k; ++i) {
    cnt.set(s[i], (cnt.get(s[i]) ?? 0) + 1);
  }
  let ans = cnt.size === k ? 1 : 0;
  for (let i = k; i < n; ++i) {
    cnt.set(s[i], (cnt.get(s[i]) ?? 0) + 1);
    cnt.set(s[i - k], (cnt.get(s[i - k]) ?? 0) - 1);
    if (cnt.get(s[i - k]) === 0) {
      cnt.delete(s[i - k]);
    }
    ans += cnt.size === k ? 1 : 0;
  }
  return ans;
}

class Solution {
  /**
   * @param String $s
   * @param Integer $k
   * @return Integer
   */
  function numKLenSubstrNoRepeats($s, $k) {
    $sum = ($k * ($k + 1)) / 2 - $k;
    $cnt = $tmp = 0;
    for ($i = 0; $i < strlen($s) - $k + 1; $i++) {
      $str = substr($s, $i, $k);
      for ($j = 0; $j < $k; $j++) {
        $tmp += strpos($str, $str[$j]);
      }
      if ($tmp === $sum) {
        $cnt++;
      }
      $tmp = 0;
    }
    return $cnt;
  }
}

Solution 2

class Solution:
  def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:
    n = len(s)
    if k > n:
      return 0
    cnt = Counter(s[:k])
    ans = int(len(cnt) == k)
    for i in range(k, n):
      cnt[s[i]] += 1
      cnt[s[i - k]] -= 1
      if cnt[s[i - k]] == 0:
        cnt.pop(s[i - k])
      ans += len(cnt) == k
    return ans

class Solution {
  public int numKLenSubstrNoRepeats(String s, int k) {
    int n = s.length();
    if (k > n) {
      return 0;
    }
    Map<Character, Integer> cnt = new HashMap<>(k);
    for (int i = 0; i < k; ++i) {
      cnt.merge(s.charAt(i), 1, Integer::sum);
    }
    int ans = cnt.size() == k ? 1 : 0;
    for (int i = k; i < n; ++i) {
      cnt.merge(s.charAt(i), 1, Integer::sum);
      if (cnt.merge(s.charAt(i - k), -1, Integer::sum) == 0) {
        cnt.remove(s.charAt(i - k));
      }
      ans += cnt.size() == k ? 1 : 0;
    }
    return ans;
  }
}

class Solution {
public:
  int numKLenSubstrNoRepeats(string s, int k) {
    int n = s.size();
    if (k > n) {
      return 0;
    }
    unordered_map<char, int> cnt;
    for (int i = 0; i < k; ++i) {
      cnt[s[i]]++;
    }
    int ans = cnt.size() == k ? 1 : 0;
    for (int i = k; i < n; ++i) {
      cnt[s[i]]++;
      cnt[s[i - k]]--;
      if (cnt[s[i - k]] == 0) {
        cnt.erase(s[i - k]);
      }
      ans += cnt.size() == k ? 1 : 0;
    }
    return ans;
  }
};

func numKLenSubstrNoRepeats(s string, k int) (ans int) {
  n := len(s)
  if k > n {
    return 0
  }
  cnt := map[byte]int{}
  for i := 0; i < k; i++ {
    cnt[s[i]]++
  }
  if len(cnt) == k {
    ans++
  }
  for i := k; i < n; i++ {
    cnt[s[i]]++
    cnt[s[i-k]]--
    if cnt[s[i-k]] == 0 {
      delete(cnt, s[i-k])
    }
    if len(cnt) == k {
      ans++
    }
  }
  return
}