Given 3 positive integers N, M, and K. the task is to construct a string of length N consisting of lowercase letters such that each substring of length M having exactly K distinct letters.
Examples:
Input: N = 5, M = 2, K = 2
Output: abade
Explanation:
Each substring of size 2 “ab”, “ba”, “ad”, “de” have 2 distinct letters.
Input: N = 7, M = 5, K = 3
Output: abcaaab
Explanation:
Each substring of size 5 “tleel”, “leelt”, “eelte” have 3 distinct letters.
Approach: In a string of size N, every substring of size M must contain exactly K distinct letters-
- Construct a string having K distinct alphabets starting from ‘a’ to ‘z’ up to the size of M and put the rest of letters like ‘a’..
- Since we have generated a string of size M with K distinct value. Now, keep repeating it till we reach string size of N.
Below is the implementation of the above approach:
C++
// C++ program to generate a string of size N// whose each substring of size M// has exactly K distinct characters#include <bits/stdc++.h>using namespace std;// Function to generate the stringstring generateString(int N, int M, int K){ // Declare empty string string s = ""; // counter for M int cnt1 = 0; // counter for K int cnt2 = 0; // Loop to generate string size of N for (int i = 0; i < N; i++) { cnt1++; cnt2++; // Generating K distinct // letters one by one if (cnt1 <= M) { if (cnt2 <= K) { s = s + char(96 + cnt1); } // After generating b distinct letters, // append rest a-b letters as 'a' else { s = s + 'a'; } } // Reset the counter value // and repeat the process else { cnt1 = 1; cnt2 = 1; s = s + 'a'; } } // return final result string return s;}// Driver codeint main(){ int N = 7, M = 5, K = 3; cout << generateString(N, M, K) << endl; return 0;} |
Java
// Java program to generate a String of size N // whose each subString of size M // has exactly K distinct characters import java.util.*;class GFG{ // Function to generate the String static String generateString(int N, int M, int K) { // Declare empty String String s = ""; // counter for M int cnt1 = 0; // counter for K int cnt2 = 0; // Loop to generate String size of N for (int i = 0; i < N; i++) { cnt1++; cnt2++; // Generating K distinct // letters one by one if (cnt1 <= M) { if (cnt2 <= K) { s = s + (char)(96 + cnt1); } // After generating b distinct letters, // append rest a-b letters as 'a' else { s = s + 'a'; } } // Reset the counter value // and repeat the process else { cnt1 = 1; cnt2 = 1; s = s + 'a'; } } // return final result String return s; } // Driver code public static void main(String[] args) { int N = 7, M = 5, K = 3; System.out.println(generateString(N, M, K)); }} // This code is contributed by 29AjayKumar |
Python3
# Python3 program to generate a string of size N# whose each substring of size M# has exactly K distinct characters# Function to generate the stringdef generateString(N, M, K): # Declare empty string s = "" # counter for M cnt1 = 0 # counter for K cnt2 = 0 # Loop to generate string size of N for i in range (N): cnt1 += 1 cnt2 += 1 # Generating K distinct # letters one by one if (cnt1 <= M): if (cnt2 <= K): s = s + chr(96 + cnt1) # After generating b distinct letters, # append rest a-b letters as 'a' else: s = s + 'a' # Reset the counter value # and repeat the process else: cnt1 = 1 cnt2 = 1 s = s + 'a' # return final result string return s# Driver codeif __name__ == "__main__": N = 7 M = 5 K = 3 print (generateString(N, M, K)) # This code is contributed by Chitranayal |
C#
// C# program to generate a String of // size N whose each subString of size // M has exactly K distinct characters using System;class GFG{ // Function to generate the String static String generateString(int N, int M, int K) { // Declare empty String String s = ""; // Counter for M int cnt1 = 0; // Counter for K int cnt2 = 0; // Loop to generate String size of N for(int i = 0; i < N; i++) { cnt1++; cnt2++; // Generating K distinct // letters one by one if (cnt1 <= M) { if (cnt2 <= K) { s = s + (char)(96 + cnt1); } // After generating b distinct letters, // append rest a-b letters as 'a' else { s = s + 'a'; } } // Reset the counter value // and repeat the process else { cnt1 = 1; cnt2 = 1; s = s + 'a'; } } // Return readonly result String return s; } // Driver code public static void Main(String[] args) { int N = 7, M = 5, K = 3; Console.WriteLine(generateString(N, M, K)); }} // This code is contributed by Rajput-Ji |
Javascript
<script>// Javascript program to generate// a String of size N// whose each subString of size M// has exactly K distinct characters // Function to generate the String function generateString(N,M,K) { // Declare empty string let s = ""; // counter for M let cnt1 = 0; // counter for K let cnt2 = 0; // Loop to generate string size of N for (let i = 0; i < N; i++) { cnt1++; cnt2++; // Generating K distinct // letters one by one if (cnt1 <= M) { if (cnt2 <= K) { s = s + String.fromCharCode(96 + cnt1); } // After generating b distinct letters, // append rest a-b letters as 'a' else { s = s + 'a'; } } // Reset the counter value // and repeat the process else { cnt1 = 1; cnt2 = 1; s = s + 'a'; } } // return final result string return s; } // Driver code let N = 7, M = 5, K = 3; document.write( generateString(N, M, K)) // This code is contributed // by avanitrachhadiya2155 </script> |
Output:
abcaaab
Time complexity: O(N)
Space complexity: O(1)
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
… [Trackback]
[…] Read More on that Topic: geeksforgeeks.org/generate-a-string-of-size-n-whose-each-substring-of-size-m-has-exactly-k-distinct-characters/ […]