Check Repeated Substring with K Replacements

Time: O(n)

Space: O(n)

Intuition

The target structure is a string made by repeating one block of length k. If the string length is not divisible by k, such a structure is impossible. Otherwise, split the string into k-length blocks. The string is already valid when all blocks are the same, and it can be fixed with one block replacement when exactly two distinct block patterns exist and one of them occurs only once.

Algorithm

1Let n = s.length(). If n is not divisible by k, return false.
2Traverse s in jumps of k and count each substring s[i..i+k) in a hash map.
3If the map has one key, every block already matches, so return true.
4If the map has more than two keys, one replacement cannot make all blocks equal, so return false.
5For exactly two keys, return true if either frequency is 1 or totalBlocks - 1.
6Otherwise, return false.

Example Walkthrough

Input: s = "abcabcxyzabc", k = 3

1.The length 12 is divisible by k = 3, so split into four blocks.
2.Blocks are ["abc", "abc", "xyz", "abc"].
3.There are exactly two distinct blocks: "abc" appears 3 times and "xyz" appears once.
4.Replacing the lone "xyz" block with "abc" makes every block equal, so the answer is true.

Output: true

Common Pitfalls

•Check divisibility by k before creating fixed-size blocks.
•Counting character mismatches is unnecessary here; the implementation works at block level.
•With more than two distinct block patterns, one replacement cannot normalize the string.

Check Repeated Substring with K Replacements.java

Java

// Approach: Split the string into blocks of length k and count distinct block frequencies.
// The string is valid if all blocks already match, or if exactly two block patterns exist
// and one of them appears once, meaning one block replacement can make all blocks equal.
// Time: O(n) Space: O(n)

import java.util.*;

class Solution {

    public boolean kSubstr(String s, int k) {
        int n = s.length();
        if (n % k != 0) {
            return false;
        }

        Map<String, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i += k) {
            String sub = s.substring(i, i + k);
            map.put(sub, map.getOrDefault(sub, 0) + 1);
        }

        if (map.size() == 1) {
            return true;
        }
        if (map.size() != 2) {
            return false;
        }

        for (int val : map.values()) {
            if (val == 1 || val == (n / k - 1)) {
                return true;
            }
        }
        return false;
    }
}

Was this solution helpful?