1100. Find K-Length Substrings With No Repeated Characters

leetcode medium

#array#csharp#leetcode#medium#search#string#tree

Task

Дана строка s и целое число k. Верните количество подстрок в s длиной k, которые не содержат повторяющихся символов.

Пример:

Input: s = "havefunonleetcode", k = 5

Output: 6

Explanation: There are 6 substrings they are: 'havef','avefu','vefun','efuno','etcod','tcode'.

C# solution

matched/original

public class Solution {
    public int NumKLenSubstrNoRepeats(string s, int k) {
        if (k > 26) return 0;
        
        int answer = 0;
        int n = s.Length;
        
        for (int i = 0; i <= n - k; i++) {
            int[] freq = new int[26];
            bool isUnique = true;
            
            for (int j = i; j < i + k; j++) {
                freq[s[j] - 'a']++;
                
                if (freq[s[j] - 'a'] > 1) {
                    isUnique = false;
                    break;
                }
            }
            
            if (isUnique) answer++;
        }
        
        return answer;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int NumKLenSubstrNoRepeats(string s, int k) {
        if (k > 26) return 0;
        
        int answer = 0;
        int n = s.size();
        
        for (int i = 0; i <= n - k; i++) {
            vector<int>& freq = new int[26];
            bool isUnique = true;
            
            for (int j = i; j < i + k; j++) {
                freq[s[j] - 'a']++;
                
                if (freq[s[j] - 'a'] > 1) {
                    isUnique = false;
                    break;
                }
            }
            
            if (isUnique) answer++;
        }
        
        return answer;
    }
}

Java solution

auto-draft, review before submit

import java.util.*;
import java.math.*;

// Auto-generated Java draft from the C# solution. Review API differences before LeetCode submit.
public class Solution {
    public int NumKLenSubstrNoRepeats(String s, int k) {
        if (k > 26) return 0;
        
        int answer = 0;
        int n = s.length;
        
        for (int i = 0; i <= n - k; i++) {
            int[] freq = new int[26];
            boolean isUnique = true;
            
            for (int j = i; j < i + k; j++) {
                freq[s[j] - 'a']++;
                
                if (freq[s[j] - 'a'] > 1) {
                    isUnique = false;
                    break;
                }
            }
            
            if (isUnique) answer++;
        }
        
        return answer;
    }
}

Python solution

matched/original

class Solution:
    def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:
        if k > 26:
            return 0
        
        n = len(s)
        answer = 0
        
        for i in range(n - k + 1):
            freq = [0] * 26
            is_unique = True
            
            for j in range(i, i + k):
                freq[ord(s[j]) - ord('a')] += 1
                
                if freq[ord(s[j]) - ord('a')] > 1:
                    is_unique = False
                    break
            
            if is_unique:
                answer += 1
        
        return answer

Go solution

matched/original

func numKLenSubstrNoRepeats(s string, k int) int {
    if k > 26 {
        return 0
    }
    
    n := len(s)
    answer := 0
    
    for i := 0; i <= n - k; i++ {
        freq := make([]int, 26)
        isUnique := true
        
        for j := i; j < i + k; j++ {
            freq[s[j] - 'a']++
            
            if freq[s[j] - 'a'] > 1 {
                isUnique = false
                break
            }
        }
        
        if isUnique {
            answer++
        }
    }
    
    return answer
}

Explanation

Algorithm

Если k > 26, верните 0, так как не может быть строки длиной более 26 символов с уникальными символами. Для остальных случаев, где k <= 26, проверьте каждую подстроку длиной k на наличие повторяющихся символов.

Итерация по строке s от индекса 0 до n - k (включительно), где n - длина строки s:

Для каждого индекса i:

Инициализируйте флаг isUnique как true и массив частот размером 26 для подсчета частот каждого символа.

Итерируйте следующие k символов и увеличивайте частоту каждого встреченного символа в массиве частот.

Если частота любого символа становится больше 1, установите isUnique в false и прекратите итерацию.

Если после итерации по k символам флаг isUnique все еще равен true, увеличьте счетчик ответов на 1.

Верните количество подстрок без повторяющихся символов после итерации по всем индексам от 0 до n - k.

😎