Skip to content

3709. Find Special Substring Of Length K

3709. Find Special Substring of Length K

Easy

You are given a string s and an integer k.

Determine if there exists a substring of length exactly k in s that satisfies the following conditions:

  1. The substring consists of only one distinct character (e.g., "aaa" or "bbb").
  2. If there is a character immediately before the substring, it must be different from the character in the substring.
  3. If there is a character immediately after the substring, it must also be different from the character in the substring.

Return true if such a substring exists. Otherwise, return false.

 

Example 1:

Input: s = "aaabaaa", k = 3

Output: true

Explanation:

The substring s[4..6] == "aaa" satisfies the conditions.

  • It has a length of 3.
  • All characters are the same.
  • The character before "aaa" is 'b', which is different from 'a'.
  • There is no character after "aaa".

Example 2:

Input: s = "abc", k = 2

Output: false

Explanation:

There is no substring of length 2 that consists of one distinct character and satisfies the conditions.

 

Constraints:

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

Solution

class Solution {
    public boolean hasSpecialSubstring(String s, int k) {
        int n = s.length();
        TreeSet<Character> set = new TreeSet<>();
        HashMap<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < k; i++) {
            set.add(s.charAt(i));
            map.put(s.charAt(i), map.getOrDefault(s.charAt(i), 0) + 1);
        }
        int start = 0;
        if (map.size() == 1 && k < n && s.charAt(k) != set.first()) return true;
        if (map.size() == 1 && k >= n) return true; 
        System.out.println(map);
        for (int i = k; i < n; i++) {
            map.put(s.charAt(start), map.getOrDefault(s.charAt(start), 0) -1);
            if (map.getOrDefault(s.charAt(start), 0) == 0) {
                map.remove(s.charAt(start));
                set.remove(s.charAt(start));
            }
            map.put(s.charAt(i), map.getOrDefault(s.charAt(i), 0) + 1);
            set.add(s.charAt(i));
            if (map.size() == 1) {
                if (start >= 0 && s.charAt(start) != set.first() && i + 1 < n && set.first() != s.charAt(i + 1)) return true;
                else if (start < 0 && i + 1 < n && s.charAt(i + 1) != set.first()) return true;
                else if (start >= 0 && i + 1 >= n && s.charAt(start) != set.first()) return true;
            }
            System.out.println(map);
            start++;
        }
        return false;
    }
}

Complexity Analysis

  • Time Complexity: O(?)
  • Space Complexity: O(?)

Explanation

[Add detailed explanation here]