Count Complete Substrings

hard

Last Updated - 29/08/2024

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 k times.
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