Given string str of size N and two integers M and K (N is divisible by M), the task is to find the Kth non-overlapping substring of size M after sorting the given string lexicographically
Examples:
Input: str = “hwnriw”, M = 3, K = 1
Output: hin
Explanation: Non overlapping substrings of size 3 after sorting are “hin” “rww”.
So 1st string is “hin” .Input: str = “xeabcks”, M = 3, K = 1
Output: abc
Naive Approach: The basic idea to solve the problem is to Sort the entire string and after that find the Kth non-overlapping substring which starts from the index (K-1)*M.
Follow the below steps to solve the problem:
- Sort the entire string.
- Get the starting index of the Kth substring as mentioned below.
- And after that take the substring of size M from that index.
Below is the implementation of the above approach:
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to get the kth substringstring getKthString(int N, int M, int K, string str){ // Sort the entire string sort(str.begin(), str.end()); // Get the starting index of the kth // lexicographically string int startingIndex = (K - 1) * M; string kthString = ""; // To track the size of string int size = 0; // Run a loop till size is not equal to M for (int i = startingIndex; i < N && size < M; i++) { // Add the current character to the // resulting string kthString += str[i]; // Increase the size by 1 size++; } // Return the resultant string return kthString;}// Driver Functionint main(){ int N = 6; int M = 3; int K = 1; string str = "xeabcks"; // Function call cout << getKthString(N, M, K, str); return 0;} |
Java
// Java code to implement the approachimport java.io.*;import java.util.*;class GFG{ // Function to get the kth substring public static String getKthString(int N, int M, int K, String str) { // Sort the entire string char tempArray[] = str.toCharArray(); Arrays.sort(tempArray); str = new String(tempArray); // Get the starting index of the kth // lexicographically string int startingIndex = (K - 1) * M; String kthString = ""; // To track the size of string int size = 0; // Run a loop till size is not equal to M for (int i = startingIndex; i < N && size < M; i++) { // Add the current character to the // resulting string kthString += str.charAt(i); // Increase the size by 1 size++; } // Return the resultant string return kthString; } public static void main(String[] args) { int N = 6; int M = 3; int K = 1; String str = "xeabcks"; // Function call System.out.print(getKthString(N, M, K, str)); }}// This code is contributed by Rohit Pradhan |
Python3
# Python3 code to implement the approach# Function to get the kth substringdef getKthString(N, M, K, str): # Sort the entire string # We do this by converting the string to a list, # then sorting the list # then joining the list back # into a string str = "".join(sorted(list(str))) # Get the starting index of the kth # lexicographically string startingIndex= (K - 1) * M kthString = "" # To track the size of string size = 0 i = startingIndex # Run a loop till size is not equal to M while (i < N and size < M): # Add the current character to the # resulting string kthString += str[i] # Increase the size by 1 size += 1 i += 1 # Return the resultant string return kthString# Driver FunctionN = 6M = 3K = 1str = "xeabcks"# Function Callprint(getKthString(N, M, K, str))# This code is contributed by phasing17. |
C#
// C# code to implement the approachusing System;class GFG { // Function to get the kth substring static String getKthString(int N, int M, int K, string str) { // Sort the entire string char[] tempArray = new char[str.Length]; for (int i = 0; i < str.Length; i++) { tempArray[i] = str[i]; } Array.Sort(tempArray); str = new string(tempArray); // Get the starting index of the kth // lexicographically string int startingIndex = (K - 1) * M; string kthString = ""; // To track the size of string int size = 0; // Run a loop till size is not equal to M for (int i = startingIndex; i < N && size < M; i++) { // Add the current character to the // resulting string kthString += str[i]; // Increase the size by 1 size++; } // Return the resultant string return kthString; } public static int Main() { int N = 6; int M = 3; int K = 1; string str = "xeabcks"; // Function call Console.Write(getKthString(N, M, K, str)); return 0; }}// This code is contributed by Taranpreet |
Javascript
<script> // Function to get the kth substring function getKthstring(N, M, K, str) { str = [...str]; // Sort the entire string str.sort(); // Get the starting index of the kth // lexicographically string int startingIndex = (K - 1) * M; int kthstring = ""; // To track the size of string int size = 0; // Run a loop till size is not equal to M for (int i = startingIndex; i < N && size < M; i++) { // Add the current character to the // resulting string kthstring += str[i]; // Increase the size by 1 size++; } // Return the resultant string return kthstring; } // Driver code let N = 6; let M = 3; let K = 1; let str = "xeabcks"; // Function call document.write(getKthstring(N, M, K, str)); // This code is contributed by sanjoy_62.</script> |
Output
abc
Time Complexity: O(N * Log N)
Auxiliary Space: O(1)
Efficient Approach: The problem can be solved efficiently using hashing and prefix sum based on the following idea:
There are total (K-1)*M characters before the starting character of the Kth substring.
So store the frequency of all the characters. Then iterate from the smallest character present in the string and with the help of prefix sum find the first character of the Kth substring.
This will help solve the problem in linear time complexity.
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to get the kth substringstring getKthString(int N, int M, int K, string str){ int a[26] = { 0 }; // Storing the frequency of all the characters for (int i = 0; i < N; i++) { a[str[i] - 'a']++; } // Prefix array int prefix[26]; prefix[0] = a[0]; for (int i = 1; i < 26; i++) { prefix[i] = prefix[i - 1] + a[i]; } // Get the starting index of the kth // lexicographically string int startingIndex = (K - 1) * M; int var = 0; // To track the size of string int size = 0; string kthString = ""; for (int i = 0; i < 26; i++) { // Prefix array is smaller than // startingIndex or element is not present if (prefix[i] < startingIndex || a[i] == 0) { continue; } // This case is when prefix array // exceeds the startingIndex for // the first time else if (var == 0) { var = prefix[i] - startingIndex; for (int j = 0; j < var; j++) { kthString += char(97 + i); size++; if (size == M) break; } } // Prefix array exceeding startingIndex // other than first time else { for (int j = 0; j < prefix[i] - prefix[i - 1]; j++) { kthString += char(97 + i); size++; if (size == M) break; } } // Breaking from the loop if we // get the string of M size if (size == M) break; } // Return the resultant string return kthString;}// Driver Functionint main(){ int N = 6; int M = 3; int K = 1; string str = "xeabck"; // Function call cout << getKthString(N, M, K, str); return 0;}// This code is contributed by Pushpesh Raj |
Java
/*package whatever //do not write package name here */import java.io.*;class GFG { public static String getKthString(int N, int M, int K, String str) { int[] a = new int[26]; // Storing the frequency of all the characters for (int i = 0; i < N; i++) { a[str.charAt(i) - 'a']++; } // Prefix array int[] prefix = new int[26]; prefix[0] = a[0]; for (int i = 1; i < 26; i++) { prefix[i] = prefix[i - 1] + a[i]; } // Get the starting index of the kth // lexicographically string int startingIndex = (K - 1) * M; int var = 0; // To track the size of string int size = 0; String kthString = ""; for (int i = 0; i < 26; i++) { // Prefix array is smaller than // startingIndex or element is not present if (prefix[i] < startingIndex || a[i] == 0) { continue; } // This case is when prefix array // exceeds the startingIndex for // the first time else if (var == 0) { var = prefix[i] - startingIndex; for (int j = 0; j < var; j++) { kthString += (char)(97 + i); size++; if (size == M) break; } } // Prefix array exceeding startingIndex // other than first time else { for (int j = 0; j < prefix[i] - prefix[i - 1]; j++) { kthString += (char)(97 + i); size++; if (size == M) break; } } // Breaking from the loop if we // get the string of M size if (size == M) break; } // Return the resultant string return kthString; } // Driver Code public static void main(String[] args) { int N = 6; int M = 3; int K = 1; String str = "xeabck"; // Function call System.out.println(getKthString(N, M, K, str)); }}//This code is contributed by KaaL-EL |
Python3
# Python program for the above approach:## Function to get the kth substringdef getKthString(N, M, K, str): a = [0]*26 ## Storing the frequency of all the characters for i in range(N): a[ord(str[i]) - ord('a')]+=1 ## Prefix array prefix = [0]*26 prefix[0] = a[0] for i in range(1, 26): prefix[i] = prefix[i - 1] + a[i] ## Get the starting index of the kth ## lexicographically string startingIndex = (K - 1) * M var = 0 ## To track the size of string size = 0 kthString = "" for i in range(26): ## Prefix array is smaller than ## startingIndex or element is not present if (prefix[i] < startingIndex or a[i] == 0): continue ## This case is when prefix array ## exceeds the startingIndex for ## the first time elif (var == 0): var = prefix[i] - startingIndex; for j in range(var): kthString += chr(97 + i) size+=1 if (size == M): break ## Prefix array exceeding startingIndex ## other than first time else: for j in range(prefix[i] - prefix[i - 1]): kthString += chr(97 + i); size += 1 if (size == M): break ## Breaking from the loop if we ## get the string of M size if (size == M): break ## Return the resultant string return kthString## Driver codeif __name__ == '__main__': N = 6; M = 3 K = 1 string = "xeabck" ## Function call print(getKthString(N, M, K, string)) # This code is contributed by entertain2022. |
C#
// C# program to implement above approachusing System;using System.Collections;using System.Collections.Generic;class GFG{ public static String getKthString(int N, int M, int K, String str) { int[] a = new int[26]; // Storing the frequency of all the characters for (int i = 0; i < N; i++) { a[(int)str[i] - (int)('a')]++; } // Prefix array int[] prefix = new int[26]; prefix[0] = a[0]; for (int i = 1 ; i < 26 ; i++) { prefix[i] = prefix[i - 1] + a[i]; } // Get the starting index of the kth // lexicographically string int startingIndex = (K - 1) * M; int var = 0; // To track the size of string int size = 0; String kthString = ""; for (int i = 0 ; i < 26 ; i++) { // Prefix array is smaller than // startingIndex or element is not present if (prefix[i] < startingIndex || a[i] == 0) { continue; } // This case is when prefix array // exceeds the startingIndex for // the first time else if (var == 0) { var = prefix[i] - startingIndex; for (int j = 0 ; j < var ; j++) { kthString += (char)(97 + i); size++; if (size == M){ break; } } } // Prefix array exceeding startingIndex // other than first time else { for (int j = 0 ; j < prefix[i] - prefix[i - 1] ; j++) { kthString += (char)(97 + i); size++; if (size == M){ break; } } } // Breaking from the loop if we // get the string of M size if (size == M){ break; } } // Return the resultant string return kthString; } public static void Main(string[] args) { int N = 6; int M = 3; int K = 1; String str = "xeabck"; // Function call Console.WriteLine(getKthString(N, M, K, str)); }}// This code is contributed by subhamgoyal2014. |
Javascript
// JavaScript program for the above approach:// Function to get the kth substringfunction getKthString(N, M, K, str){ let a = new Array(26).fill(0); // Storing the frequency of all the characters for (var i = 0; i < N; i++) a[str[i].charCodeAt(0) - 'a'.charCodeAt(0)]++; // Prefix array let prefix = new Array(26).fill(0); prefix[0] = a[0]; for (var i = 1; i < 26; i++) prefix[i] = prefix[i - 1] + a[i]; // Get the starting index of the kth // lexicographically string let startingIndex = (K - 1) * M; let var_ = 0; // To track the size of string let size = 0; let kthString = ""; for (var i = 0; i < 26; i++) { // Prefix array is smaller than // startingIndex or element is not present if (prefix[i] < startingIndex || a[i] == 0) continue; // This case is when prefix array // exceeds the startingIndex for // the first time else if (var_ == 0) { var_ = prefix[i] - startingIndex; for (var j = 0; j < var_; j++) { kthString += String.fromCharCode(97 + i); size += 1; if (size == M) break; } } // Prefix array exceeding startingIndex // other than first time else { for (var j = 0; j < (prefix[i] - prefix[i - 1]); j++) { kthString += String.fromCharCode(97 + i); size += 1; if (size == M) break; } } // Breaking from the loop if we // get the string of M size if (size == M) break } // Return the resultant string return kthString;}// Driver codelet N = 6;let M = 3;let K = 1;let string = "xeabck";// Function callconsole.log(getKthString(N, M, K, string)); // This code is contributed by phasing17 |
Output
abc
Time Complexity: O(N)
Auxiliary Space: O(N)
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!
Share your thoughts in the comments
