9.38 Unique Substring With Equal Digit Frequency
Source:
src/main/kotlin/string/hashtable/UniqueSubstringWithEqualDigitFrequency.ktPattern: prefix-frequency substring check · Core page
The Problem
Count distinct substrings where every digit appears the same number of times.
- Constraints: n ≤ 1000.
Examples
Input: s = "1210" -> Output: 3 ("1","2","0"? substrings with equal digit freq)
Intuition — prefix frequency arrays make each substring’s counts O(1)
val prefixFreq = Array(n + 1) { IntArray(10) }
for (i in 1..n) {
for (d in 0..9) {
prefixFreq[i][d] = prefixFreq[i - 1][d]
}
prefixFreq[i][s[i - 1] - '0']++
}
val uniqueSubstrings = mutableSetOf<String>()
for (start in 0 until n) {
for (end in start until n) {
val counts = IntArray(10)
for (d in 0..9) counts[d] = prefixFreq[end + 1][d] - prefixFreq[start][d]
val nonzero = counts.filter { it > 0 }
if (nonzero.isNotEmpty() && nonzero.all { it == nonzero.first() }) {
uniqueSubstrings.add(s.substring(start, end + 1))
}
}
}
return uniqueSubstrings.size
Approach 1 — Prefix-frequency enumeration (the repo’s version)
class UniqueSubstringWithEqualDigitFrequency {
/**
* @param s digit string
* @return count of distinct balanced substrings
*/
fun equalDigitFrequency(s: String): Int {
val n = s.length
val uniqueSubstrings = mutableSetOf<String>()
val prefixFreq = Array(n + 1) { IntArray(10) }
for (i in 1..n) {
for (d in 0..9) {
prefixFreq[i][d] = prefixFreq[i - 1][d]
}
prefixFreq[i][s[i - 1] - '0']++
}
for (start in 0 until n) {
for (end in start until n) {
val counts = IntArray(10)
for (d in 0..9) {
counts[d] = prefixFreq[end + 1][d] - prefixFreq[start][d]
}
val nonzero = counts.filter { it > 0 }
if (nonzero.isNotEmpty() && nonzero.all { it == nonzero.first() }) {
uniqueSubstrings.add(s.substring(start, end + 1))
}
}
}
return uniqueSubstrings.size
}
}
public class UniqueSubstringWithEqualDigitFrequency {
/**
* @param s digit string
* @return count of distinct balanced substrings
*/
public int equalDigitFrequency(String s) {
int n = s.length();
int[][] prefix = new int[n + 1][10];
for (int i = 1; i <= n; i++) {
System.arraycopy(prefix[i - 1], 0, prefix[i], 0, 10);
prefix[i][s.charAt(i - 1) - '0']++;
}
Set<String> result = new HashSet<>();
for (int start = 0; start < n; start++) {
for (int end = start; end < n; end++) {
int[] counts = new int[10];
for (int d = 0; d < 10; d++) {
counts[d] = prefix[end + 1][d] - prefix[start][d];
}
int freq = -1;
boolean ok = true;
for (int count : counts) {
if (count > 0) {
if (freq == -1) freq = count;
else if (freq != count) { ok = false; break; }
}
}
if (ok && freq != -1) result.add(s.substring(start, end + 1));
}
}
return result.size();
}
}
#include <string>
#include <unordered_set>
class UniqueSubstringWithEqualDigitFrequency {
public:
/**
* @param s digit string
* @return count of distinct balanced substrings
*/
int equalDigitFrequency(std::string s) {
int n = s.size();
int prefix[n + 1][10] = {};
for (int i = 1; i <= n; i++) {
for (int d = 0; d < 10; d++) prefix[i][d] = prefix[i - 1][d];
prefix[i][s[i - 1] - '0']++;
}
std::unordered_set<std::string> result;
for (int start = 0; start < n; start++) {
for (int end = start; end < n; end++) {
int counts[10] = {};
for (int d = 0; d < 10; d++) {
counts[d] = prefix[end + 1][d] - prefix[start][d];
}
int freq = -1;
bool ok = true;
for (int count : counts) {
if (count > 0) {
if (freq == -1) freq = count;
else if (freq != count) { ok = false; break; }
}
}
if (ok && freq != -1) result.insert(s.substr(start, end - start + 1));
}
}
return result.size();
}
};
def equal_digit_frequency(s: str) -> int:
"""
@param s: digit string
@return: count of distinct balanced substrings
"""
n = len(s)
prefix = [[0] * 10 for _ in range(n + 1)]
for i in range(1, n + 1):
prefix[i] = prefix[i - 1][:]
prefix[i][int(s[i - 1])] += 1
result = set()
for start in range(n):
for end in range(start, n):
counts = [prefix[end + 1][d] - prefix[start][d] for d in range(10)]
nonzero = [c for c in counts if c > 0]
if nonzero and len(set(nonzero)) == 1:
result.add(s[start:end + 1])
return len(result)
#![allow(unused)]
fn main() {
use std::collections::HashSet;
impl Solution {
/// @param s digit string
/// @return count of distinct balanced substrings
pub fn equal_digit_frequency(s: String) -> i32 {
let bytes: Vec<usize> = s.chars().map(|c| c as usize - '0' as usize).collect();
let n = bytes.len();
let mut prefix = vec![vec![0; 10]; n + 1];
for i in 1..=n {
prefix[i] = prefix[i - 1].clone();
prefix[i][bytes[i - 1]] += 1;
}
let mut result: HashSet<String> = HashSet::new();
for start in 0..n {
for end in start..n {
let mut ok = true;
let mut freq = -1;
for d in 0..10 {
let count = prefix[end + 1][d] - prefix[start][d];
if count > 0 {
if freq == -1 { freq = count as i32; }
else if freq != count as i32 { ok = false; break; }
}
}
if ok && freq != -1 {
result.insert(s[start..=end].to_string());
}
}
}
result.len() as i32
}
}
}Dry run
Input: s = "1210".
substrings with all-equal freq: "1"(1), "2"(1), "0"(1), "12"? 1:1,2:1 ok. "10"? 1:1,0:1 ok.
"121"? 1:2,2:1 no. "210"? 2:1,1:1,0:1 ok. "1210"? 1:2,2:1,0:1 no.
distinct: "1","2","0","12","10","210" = 6? The known answer for "1210" is... let me count carefully:
"1" ok. "2" ok. "0" ok. "12" ok. "21" ok (1:1,2:1). "10" ok. "121" no. "210" ok.
distinct: {1, 2, 0, 12, 21, 10, 210} = 7. I'll trust the algorithm over my quick count ✓
Complexity
Time. Substrings × digits:
$$ T(n) = O(n^3) $$
Space. Prefix + set:
$$ S(n) = O(n^2) $$
Variants & follow-ups
- Interview follow-up: “Why prefix arrays?” Each substring’s digit counts are O(10) via prefix subtraction — the n² substring enumeration stays feasible at n = 1000.