Count distinct substrings that contain some characters at most k times

0 0 5 minutes read

Given a integer k and a string str, the task is to count the number of distinct sub-strings such that each sub-string does not contain some specific characters more than k times. The specific characters are given as another string.

Examples:

Input: str = “ababab”, anotherStr = “bcd”, k = 1
Output: 5
All valid sub-strings are “a”, “b”, “ab”, “ba” and “aba”

Input: str = “acbacbacaa”, anotherStr = “ycb”, k = 2
Output: 8

Approach:

Store characters of anotherStr in a boolean array of size 256 for quick lookip
Traverse through all substrings of given string. For every substring, keep the count of illegal characters in anotherStr.
If the count of these characters exceeds the value of k then break out of the inner loop.
Else, store this sub-string in an hash table to keep distinct substrings.

Below is the implementation of the above approach:

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
const int MAX_CHAR = 256;
 
// Function to return the count of valid sub-strings
int countSubStrings(string s, string anotherStr, int k)
{
    // Store all characters of anotherStr in a 
    // direct index table for quick lookup.
    bool illegal[MAX_CHAR] = { false };
    for (int i = 0; i < anotherStr.size(); i++)
        illegal[anotherStr[i]] = true;
 
    // To store distinct output substrings
    unordered_set<string> us;
 
    // Traverse through the given string and
    // one by one generate substrings beginning
    // from s[i].
    for (int i = 0; i < s.size(); ++i) {
 
        // One by one generate substrings ending
        // with s[j]
        string ss = "";
        int count = 0;
        for (int j = i; j < s.size(); ++j) {
 
            // If character is illegal
            if (illegal[s[j]])
                ++count;
            ss = ss + s[j];
 
            // If current substring is valid
            if (count <= k) {
                us.insert(ss);
            }
 
            // If current substring is invalid,
            // adding more characters would not
            // help.
            else
                break;
        }
    }
 
    // Return the count of distinct sub-strings
    return us.size();
}
 
// Driver code
int main()
{
    string str = "acbacbacaa";
    string anotherStr = "abcdefghijklmnopqrstuvwxyz";
    int k = 2;
    cout << countSubStrings(str, anotherStr, k);
    return 0;
}

Java

// Java implementation of the approach
import java.util.*;
 
class GFG {
 
    static int MAX_CHAR = 256;
 
    // Function to return the count of valid sub-strings
    static int countSubStrings(String s, String anotherStr, int k) 
    {
        // Store all characters of anotherStr in a 
        // direct index table for quick lookup.
        boolean illegal[] = new boolean[MAX_CHAR];
        for (int i = 0; i < anotherStr.length(); i++) 
        {
            illegal[anotherStr.charAt(i)] = true;
        }
 
        // To store distinct output substrings
        HashSet<String> us = new HashSet<String>();
 
        // Traverse through the given string and
        // one by one generate substrings beginning
        // from s[i].
        for (int i = 0; i < s.length(); ++i) 
        {
 
            // One by one generate substrings ending
            // with s[j]
            String ss = "";
            int count = 0;
            for (int j = i; j < s.length(); ++j) 
            {
 
                // If character is illegal
                if (illegal[s.charAt(j)])
                {
                    ++count;
                }
                ss = ss + s.charAt(j);
 
                // If current substring is valid
                if (count <= k) 
                {
                    us.add(ss);
                } 
                 
                // If current substring is invalid,
                // adding more characters would not
                // help.
                else
                {
                    break;
                }
            }
        }
 
        // Return the count of distinct sub-strings
        return us.size();
    }
 
    // Driver code
    public static void main(String[] args) 
    {
        String str = "acbacbacaa";
        String anotherStr = "abcdefghijklmnopqrstuvwxyz";
        int k = 2;
        System.out.println(countSubStrings(str, anotherStr, k));
    }
}
 
// This code is contributed by PrinciRaj1992

Python3

# Python3 implementation of the approach 
 
MAX_CHAR = 256
 
# Function to return the count
# of valid sub-strings 
def countSubStrings(s, anotherStr, k) :
     
    # Store all characters of anotherStr in
    # a direct index table for quick lookup. 
    illegal = [False] * MAX_CHAR
     
    for i in range(len(anotherStr)) :
        illegal[ord(anotherStr[i])] = True
         
    # To store distinct output substrings 
    us = set() 
     
    # Traverse through the given string 
    # and one by one generate substrings 
    # beginning from s[i]. 
    for i in range(len(s)) :
         
        # One by one generate substrings 
        # ending with s[j] 
        ss = "" 
         
        count = 0
        for j in range(i, len(s)) :
             
            # If character is illegal
            if (illegal[ord(s[j])]) :
                count += 1
            ss = ss + s[j]
             
            # If current substring is valid
            if (count <= k) :
                us.add(ss)
             
            # If current substring is invalid,
            # adding more characters would not
            # help.
            else :
                break
     
    # Return the count of distinct
    # sub-strings 
    return len(us)
 
# Driver code 
if __name__ == "__main__" : 
 
    string = "acbacbacaa"
    anotherStr = "abcdefghijklmnopqrstuvwxyz"
    k = 2
    print(countSubStrings(string, 
                          anotherStr, k))
 
# This code is contributed by Ryuga

C#

// C# implementation of the approach
using System;
using System.Collections.Generic;
 
class GFG
{
    static int MAX_CHAR = 256;
 
    // Function to return the count 
    // of valid sub-strings
    static int countSubStrings(String s, 
                        String anotherStr, int k) 
    {
         
        // Store all characters of anotherStr in a 
        // direct index table for quick lookup.
        bool []illegal = new bool[MAX_CHAR];
        for (int i = 0; i < anotherStr.Length; i++) 
        {
            illegal[anotherStr[i]] = true;
        }
 
        // To store distinct output substrings
        HashSet<String> us = new HashSet<String>();
 
        // Traverse through the given 
        // string and one by one generate 
        // substrings beginning from s[i].
        for (int i = 0; i < s.Length; ++i) 
        {
 
            // One by one generate substrings 
            // ending with s[j]
            String ss = "";
            int count = 0;
            for (int j = i; j < s.Length; ++j) 
            {
 
                // If character is illegal
                if (illegal[s[j]])
                {
                    ++count;
                }
                ss = ss + s[j];
 
                // If current substring is valid
                if (count <= k) 
                {
                    us.Add(ss);
                } 
                 
                // If current substring is invalid,
                // adding more characters would not
                // help.
                else
                {
                    break;
                }
            }
        }
 
        // Return the count of distinct sub-strings
        return us.Count;
    }
 
    // Driver code
    public static void Main() 
    {
        String str = "acbacbacaa";
        String anotherStr = "abcdefghijklmnopqrstuvwxyz";
        int k = 2;
        Console.WriteLine(countSubStrings(str, anotherStr, k));
    }
}
 
//This code is contributed by 29AjayKumar

Javascript

<script>
 
// js implementation of the approach
 
let MAX_CHAR = 256;
 
// Function to return the count of valid sub-strings
function countSubStrings( s, anotherStr, k)
{
    // Store all characters of anotherStr in a 
    // direct index table for quick lookup.
    let illegal = [];
    for(let i = 0;i<256;i++)
         illegal.push(false);
    for (let i = 0; i < anotherStr.length; i++)
        illegal[anotherStr[i]] = true;
 
    // To store distinct output substrings
    let us = new Set();
 
    // Traverse through the given string and
    // one by one generate substrings beginning
    // from s[i].
    for (let i = 0; i < s.length; ++i) {
 
        // One by one generate substrings ending
        // with s[j]
        let ss = "";
        let count = 0;
        for (let j = i; j < s.length; ++j) {
 
            // If character is illegal
            if (illegal[s[j]])
                ++count;
            ss = ss + s[j];
 
            // If current substring is valid
            if (count <= k) {
                us.add(ss);
            }
 
            // If current substring is invalid,
            // adding more characters would not
            // help.
            else
                break;
        }
    }
 
    // Return the count of distinct sub-strings
    return us.size;
}
 
// Driver code
let str = "acbacbacaa";
let anotherStr = "abcdefghijklmnopqrstuvwxyz";
let k = 2;
document.write(countSubStrings(str, anotherStr, k));
 
</script>

Output:

Time Complexity: O(max(n², m), where n and m are the length of string “str” and “anotherstr” respectively,
Auxiliary Space: O(max(n2, MAX_CHAR))

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!