[Avalara Question] Perfect Substring

Problem: Given a string s (contains only digits) and an integer k, a perfect substring is where each and every character appeared exactly k times. Write a method which returns the number of perfect substrings of string s.

Example:

Input: s = "1020122", k = 2
Output: 2
Explanation: 
"102012" and "22" 

Approach: The idea is simple. Traverse through all substrings. For each substring we can check if frequency of all the characters are exactly k then we increment the count. To count frequency, we can maintain a hash.

 

Implementation in C#:

        public static int PerfectSubstring(string s, int k)

        {

            int result = 0;

            if ( s?.Length < k)

            {

                return result;

            } 

            for (int i = 0; i < s.Length; ++i)

            {

                // It is given that the input string only contains digit so we can take array of 10 integers for hashing

                int[] frequency = new int[10];

                for (int j = i; j < s.Length; ++j)

                {

                    int index = s[j] - '0';

                    ++frequency[index];

                    // frequency of a character more than k, no need to process further

                    if (frequency[index] > k)

                    {

                        break;

                    }

                    else if (frequency[index] == k && ValidateFrequency(frequency, k))

                    {

                        ++result;

                    }

                }

            }

            return result;

        }

        private static bool ValidateFrequency(int[] frequency, int k)

        {

            for (int i = 0; i < frequency.Length; ++i)

            {

                if (frequency[i] != 0 && frequency[i] != k)

                {

                    return false;

                }

            }

            return true;

        }

Complexity: O(n^2)