Count Complete Substrings
On this page 
Problem Statement Solution 1: Brute Force with All Substrings Solution 2: Sliding Window with Hash Map Solution 3: Dynamic Programming Approach Solution 4: Prefix Frequency Array Solution 5: Efficient ASCII Difference Check Solution 6: Hash Set for Frequency Check Solution 7: Set-Based Frequency Validation Solution 8: Direct Validation with Hash Map Solution 9: Two-Pointer Approach Solution 10: Frequency Map with Early Exit More Problems Solutions
Problem Statement
You are given a string word and an integer k. Your task is to count the number of substrings of word that meet the following criteria:
Character Frequency: Each character in the substring must appear exactly
ktimes.Adjacent Characters: The absolute difference between the ASCII values of any two adjacent characters in the substring must be at most 2.
A substring is defined as a contiguous sequence of characters within the string word.
Write a function that returns the number of complete substrings.
Example 1
Input: str = "igigee" , k = 2
Output: 3
Example 2
Input: str = "pdpddpdppd" , k = 4
Output: 1
Solution 1: Brute Force with All Substrings
function countValidSubstrings(word, k) {
const length = word.length;
let count = 0;
// Function to check if all characters in the map appear exactly k times
function hasValidCharacterCounts(countMap) {
return Object.values(countMap).every(count => count === k);
}
// Iterate over all possible substrings
for (let start = 0; start < length; start++) {
const frequencyMap = {};
for (let end = start; end < length; end++) {
const char = word[end];
frequencyMap[char] = (frequencyMap[char] || 0) + 1;
if (!hasValidCharacterCounts(frequencyMap)) {
continue;
}
if (end > start && Math.abs(word.charCodeAt(end) - word.charCodeAt(end - 1)) > 2) {
break; // As soon as the ASCII difference condition fails, break out of the loop
}
if (hasValidCharacterCounts(frequencyMap)) {
count++;
}
}
}
return count;
}
const str1 = "igigee";
const k1 = 2;
countValidSubstrings(str1,k1); //output: 3
const str2 = "pdpddpdppd";
const k2 = 4;
countValidSubstrings(str2,k2); //output: 1
Solution 2: Sliding Window with Hash Map
function countValidSubstringsUsingSlidingWindow(word, k) {
function hasValidCharacterCounts(countMap) {
return Object.values(countMap).every(count => count === k);
}
let count = 0;
for (let start = 0; start < word.length; start++) {
const frequencyMap = {};
let isValid = true;
for (let end = start; end < word.length; end++) {
const char = word[end];
frequencyMap[char] = (frequencyMap[char] || 0) + 1;
if (!hasValidCharacterCounts(frequencyMap)) {
continue;
}
if (end > start && Math.abs(word.charCodeAt(end) - word.charCodeAt(end - 1)) > 2) {
isValid = false;
}
if (isValid && hasValidCharacterCounts(frequencyMap)) {
count++;
} else {
break;
}
}
}
return count;
}
const str1 = "igigee";
const k1 = 2;
countValidSubstringsUsingSlidingWindow(str1,k1); //output: 3
const str2 = "pdpddpdppd";
const k2 = 4;
countValidSubstringsUsingSlidingWindow(str2,k2); //output: 1
Solution 3: Dynamic Programming Approach
function countCompleteSubstringsWithDP(word, k) {
const length = word.length;
let count = 0;
for (let start = 0; start < length; start++) {
const frequencyMap = {};
let isValid = true;
for (let end = start; end < length; end++) {
const char = word[end];
frequencyMap[char] = (frequencyMap[char] || 0) + 1;
if (Object.values(frequencyMap).some(freq => freq > k)) {
isValid = false;
break;
}
if (Object.values(frequencyMap).every(freq => freq === k)) {
if (end > start && Math.abs(word.charCodeAt(end) - word.charCodeAt(end - 1)) > 2) {
isValid = false;
break;
}
if (isValid) {
count++;
}
}
}
}
return count;
}
const str1 = "igigee";
const k1 = 2;
countCompleteSubstringsWithDP(str1,k1); //output: 3
const str2 = "pdpddpdppd";
const k2 = 4;
countCompleteSubstringsWithDP(str2,k2); //output: 1
Solution 4: Prefix Frequency Array
function countSubstringsWithPrefixFrequency(word, k) {
const length = word.length;
let count = 0;
for (let start = 0; start < length; start++) {
const frequencyMap = {};
let valid = true;
for (let end = start; end < length; end++) {
const char = word[end];
frequencyMap[char] = (frequencyMap[char] || 0) + 1;
if (Object.values(frequencyMap).some(count => count > k)) {
valid = false;
break;
}
if (Object.values(frequencyMap).every(count => count === k)) {
if (end > start && Math.abs(word.charCodeAt(end) - word.charCodeAt(end - 1)) > 2) {
valid = false;
break;
}
if (valid) {
count++;
}
}
}
}
return count;
}
const str1 = "igigee";
const k1 = 2;
countSubstringsWithPrefixFrequency(str1,k1); //output: 3
const str2 = "pdpddpdppd";
const k2 = 4;
countSubstringsWithPrefixFrequency(str2,k2); //output: 1
Solution 5: Efficient ASCII Difference Check
function countValidSubstringsWithAsciiCheck(word, k) {
const length = word.length;
let count = 0;
// Function to check if all characters in the map appear exactly k times
function hasValidCharacterCounts(countMap) {
return Object.values(countMap).every(count => count === k);
}
// Iterate over all possible starting points
for (let start = 0; start < length; start++) {
const frequencyMap = {};
let isValid = true;
for (let end = start; end < length; end++) {
const char = word[end];
frequencyMap[char] = (frequencyMap[char] || 0) + 1;
if (!hasValidCharacterCounts(frequencyMap)) {
// If frequency count fails, move to the next start position
continue;
}
// Check ASCII difference condition
if (end > start && Math.abs(word.charCodeAt(end) - word.charCodeAt(end - 1)) > 2) {
isValid = false;
}
if (isValid && hasValidCharacterCounts(frequencyMap)) {
count++;
} else {
break; // Early exit for current starting point if not valid
}
}
}
return count;
}
const str1 = "igigee";
const k1 = 2;
countValidSubstringsWithAsciiCheck(str1,k1); //output: 3
const str2 = "pdpddpdppd";
const k2 = 4;
countValidSubstringsWithAsciiCheck(str2,k2); //output: 1
Solution 6: Hash Set for Frequency Check
function countSubstringsUsingHashSet(word, k) {
let count = 0;
for (let start = 0; start < word.length; start++) {
const frequencyMap = {};
let valid = true;
for (let end = start; end < word.length; end++) {
const char = word[end];
frequencyMap[char] = (frequencyMap[char] || 0) + 1;
if (Object.values(frequencyMap).some(count => count > k)) {
valid = false;
break;
}
if (Object.values(frequencyMap).every(count => count === k)) {
if (end > start && Math.abs(word.charCodeAt(end) - word.charCodeAt(end - 1)) > 2) {
valid = false;
break;
}
if (valid) {
count++;
}
}
}
}
return count;
}
const str1 = "igigee";
const k1 = 2;
countSubstringsUsingHashSet(str1,k1); //output: 3
const str2 = "pdpddpdppd";
const k2 = 4;
countSubstringsUsingHashSet(str2,k2); //output: 1
Solution 7: Set-Based Frequency Validation
function countSubstringsWithSetValidation(word, k) {
const length = word.length;
let count = 0;
for (let start = 0; start < length; start++) {
const frequencyMap = {};
for (let end = start; end < length; end++) {
const char = word[end];
frequencyMap[char] = (frequencyMap[char] || 0) + 1;
if (Object.values(frequencyMap).every(count => count === k)) {
if (end > start && Math.abs(word.charCodeAt(end) - word.charCodeAt(end - 1)) > 2) {
break;
}
count++;
}
}
}
return count;
}
const str1 = "igigee";
const k1 = 2;
countSubstringsWithSetValidation(str1,k1); //output: 3
const str2 = "pdpddpdppd";
const k2 = 4;
countSubstringsWithSetValidation(str2,k2); //output: 1
Solution 8: Direct Validation with Hash Map
function countSubstringsWithDirectValidation(word, k) {
const length = word.length;
let count = 0;
for (let start = 0; start < length; start++) {
const frequencyMap = {};
for (let end = start; end < length; end++) {
const char = word[end];
frequencyMap[char] = (frequencyMap[char] || 0) + 1;
if (Object.values(frequencyMap).some(count => count > k)) {
break;
}
if (Object.values(frequencyMap).every(count => count === k)) {
if (end > start && Math.abs(word.charCodeAt(end) - word.charCodeAt(end - 1)) > 2) {
break;
}
count++;
}
}
}
return count;
}
const str1 = "igigee";
const k1 = 2;
countSubstringsWithDirectValidation(str1,k1); //output: 3
const str2 = "pdpddpdppd";
const k2 = 4;
countSubstringsWithDirectValidation(str2,k2); //output: 1
Solution 9: Two-Pointer Approach
function countSubstringsUsingTwoPointers(word, k) {
let count = 0;
for (let start = 0; start < word.length; start++) {
const frequencyMap = {};
for (let end = start; end < word.length; end++) {
const char = word[end];
frequencyMap[char] = (frequencyMap[char] || 0) + 1;
if (Object.values(frequencyMap).some(count => count > k)) {
break;
}
if (Object.values(frequencyMap).every(count => count === k)) {
if (end > start && Math.abs(word.charCodeAt(end) - word.charCodeAt(end - 1)) > 2) {
break;
}
count++;
}
}
}
return count;
}
const str1 = "igigee";
const k1 = 2;
countSubstringsUsingTwoPointers(str1,k1); //output: 3
const str2 = "pdpddpdppd";
const k2 = 4;
countSubstringsUsingTwoPointers(str2,k2); //output: 1
Solution 10: Frequency Map with Early Exit
function countSubstringsWithEarlyExit(word, k) {
const length = word.length;
let count = 0;
for (let start = 0; start < length; start++) {
const frequencyMap = {};
let valid = true;
for (let end = start; end < length; end++) {
const char = word[end];
frequencyMap[char] = (frequencyMap[char] || 0) + 1;
if (Object.values(frequencyMap).some(count => count > k)) {
valid = false;
break;
}
if (Object.values(frequencyMap).every(count => count === k)) {
if (end > start && Math.abs(word.charCodeAt(end) - word.charCodeAt(end - 1)) > 2) {
valid = false;
break;
}
if (valid) {
count++;
}
}
}
}
return count;
}
const str1 = "igigee";
const k1 = 2;
countSubstringsWithEarlyExit(str1,k1); //output: 3
const str2 = "pdpddpdppd";
const k2 = 4;
countSubstringsWithEarlyExit(str2,k2); //output: 1