Given a string of lowercase alphabets, count all possible substrings (not necessarily distinct) that have exactly k distinct characters. Example 1:Input:S = "aba", K = 2Output:3Explanation:The substrings are: "ab", "ba" and "aba".
Question
Given a string of lowercase alphabets, count all possible substrings (not necessarily distinct) that have exactly k distinct characters. Example 1:Input:S = "aba", K = 2Output:3Explanation:The substrings are: "ab", "ba" and "aba".
Solution
Sure, here is a Python solution for the problem:
def count_k_dist(str1, k):
str_len = len(str1)
result = 0
ctr = [0] * 27
for i in range(0, str_len):
dist_ctr = 0
ctr = [0] * 27
for j in range(i, str_len):
if(ctr[ord(str1[j]) - 97] == 0):
dist_ctr += 1
ctr[ord(str1[j]) - 97] += 1
if(dist_ctr == k):
result += 1
if(dist_ctr > k):
break
return result
# Test the function
S = "aba"
K = 2
print(count_k_dist(S, K)) # Output: 3
Here is how the function works:
- The function
count_k_disttakes a string and an integer as input. - It initializes a counter array
ctrof size 27 (for 26 lowercase alphabets plus one). - It then starts a loop from the first character of the string.
- For each character, it resets the counter array and starts another loop from the current character to the end of the string.
- If the current character has not been encountered before (i.e., its count in
ctris 0), it incrementsdist_ctr, which keeps track of the number of distinct characters. - It then increments the count of the current character in
ctr. - If the number of distinct characters is equal to
k, it increments the result. - If the number of distinct characters is more than
k, it breaks the inner loop. - Finally, it returns the result
Similar Questions
Raju is preparing questions for the internal test. While creating questions, he gave one such question to his son Arun to solve. Raju has given the string S to his son Arun. Arun's task is to print the size of the longest possible substring that has exactly K unique characters.ExampleInput:String = aabacbebebe; K = 3Output:The substring will be cbebebe with length 7. Explanation:The unique characters in the string are: 'a', 'b', 'c', and 'e'. The longest subsequence with at most 3 distinct characters is "aabacbe". It contains the characters 'a', 'b', and 'c', which is the maximum number of distinct characters allowed (k = 3). Therefore, the length of the longest subsequence is 7.Input format :The first line of input consists of the string S.The second line of input consists of the integer K.Output format :The output prints the size of the longest possible substring that has exactly K unique characters.Refer to the sample output for the formatting specifications.Code constraints :1≤ string length ≤ 501≤ K ≤10Sample test cases :Input 1 :aabacbebebe3Output 1 :7Input 2 :abbc1Output 2 :2
Given two integers N and K, the task is to find the string S of minimum length such that it contains all possible strings of size N as a substring. The characters of the string should be from integers ranging from 0 to K-1. Example 1:Input:N = 2, K = 2Output: 00110Explanation: Allowed characters are from 0 to k-1 (i.e., 0 and 1).There are 4 string possible of size N=2 (i.e "00", "01","10","11")"00110" contains all possible string as a substring. It also has the minimum length.Example 2:Input:N = 2, K = 3Output: 0010211220Explanation: Allowed characters are from 0 to k-1 (i.e., 0, 1 and 2).There are total 9 strings possibleof size N, given output string has the minimumlength that contains all those strings as substring.Your Task: You don't need to read input or print anything. Complete the function findString( ) which takes the integer N and the integer K as input parameters and returns the string.Note: In case of multiple answers, return any string of minimum length which satisfies above condition. The driver will print the length of the string. In case of wrong answer it will print -1.Expected Time Complexity: O(KNlogK)Expected Space Complexity: O(KNN)Constraints:1 ≤ N ≤ 41 < K < 101 < KNN < 106
Problem StatementYou wish to help Ashish, who possesses a collection of N strings, some of which may be duplicated, and has been assigned the task of finding the kth unique string.If the number of unique strings is less than k, he needs to display an empty string. Considering you are Ashish's best friend can you assist him with this challenge?Input FormatThe first line contains an integer N denoting the number of strings.The next N lines contain strings.The next line contains an integer k.Output FormatThe output contains the kth distinct string. If there are less than k unique string display an empty string.Constraints1<=N<=105-10^8<=arr[i].length()<=10^8Sample Testcase 0Testcase Input6dbcbca2Testcase OutputaExplanationThe only strings in arr that are distinct are "d" and "a." The letter "d" comes first, making it the first separate string.Because "a" appears second, it is the second distinct string. "a" is returned since k == 2.
Write a program to print the duplicate characters in the given stringInput FormatGiven a stringOutput Formatprint the duplicate characters separated by space ':'Constraint :1 <= string length <= 100Note: If more than one occurred then print the first occurrencethe string might have upper case letter that should be considered as lowercase
You are given a string s consisting of lowercase letters and an integer k. We call a string t ideal if the following conditions are satisfied:t is a subsequence of the string s.The absolute difference in the alphabet order of every two adjacent letters in t is less than or equal to k.Return the length of the longest ideal string.A subsequence is a string that can be derived from another string by deleting some or no characters without changing the order of the remaining characters.Note that the alphabet order is not cyclic. For example, the absolute difference in the alphabet order of 'a' and 'z' is 25, not
Upgrade your grade with Knowee
Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.