Python: Count number of substrings from a given string of lowercase alphabets with exactly k distinct characters

Last update on December 21 2024 07:46:58 (UTC/GMT +8 hours)

Substrings with k distinct characters.

Write a Python program to count the number of substrings from a given string of lowercase alphabets with exactly k distinct (given) characters.

Sample Solution:

Python Code:

# Function to count substrings with k distinct chars
def count_k_dist(str1, k):

  # Get string length
  str_len = len(str1)
  
  result = 0

  # Character counter array
  ctr = [0] * 27

  for i in range(0, str_len):

    dist_ctr = 0
    ctr = [0] * 27

    for j in range(i, str_len):
      
      # Increment distinct char count
      if(ctr[ord(str1[j]) - 97] == 0):
        dist_ctr += 1

      # Increment char counter
      ctr[ord(str1[j]) - 97] += 1

      # Increment result if exactly k distinct
      if(dist_ctr == k):
        result += 1

      # Break loop if > k distinct  
      if(dist_ctr > k):
        break

  return result

# Get input  
str1 = input("Input a string (lowercase alphabets):")
k = int(input("Input k: "))

# Print result
print("Number of substrings with exactly", k, "distinct characters : ", end = "")
print(count_k_dist(str1, k)) 

Sample Output:

Input a string (lowercase alphabets): wolf
Input k:  4
Number of substrings with exactly 4 distinct characters : 1

Flowchart:

Python Code Editor:

Previous: Write a Python program to find smallest window that contains all characters of a given string.
Next: Write a Python program to count number of non-empty substrings of a given string.