Given a string S. The task is to print the K-th lexicographically the smallest one among the different substrings of s.
A substring of s is a string obtained by taking out a non-empty contiguous part in s.
For example, if s = ababc, a, bab and ababc are substrings of s, while ac, z, and an empty string are not. Also, we say that substrings are different when they are different as strings.
Examples:
Input: str = “aba”, k = 4
Output: b
All unique substrings are a, ab, aba, b, ba.
Thus the 4th lexicographically smallest substring is b.Input: str = “neveropen”, k = 5
Output: eeksf
Approach: For an arbitrary string t, each of its proper suffixes is lexicographically smaller than t, and the lexicographic rank of t is at least |t|. Thus, the length of the answer is at most K. Generate all substrings of s whose lengths are at most K. Sort them, unique them, and print the K-th one, where N = |S|.
Below is the implementation of the above approach:
C++
// C++ implementation of the above approach #include<bits/stdc++.h>using namespace std;void kThLexString(string st, int k, int n){ // Set to store the unique substring set<string> z; for(int i = 0; i < n; i++) { // String to create each substring string pp; for(int j = i; j < i + k; j++) { if (j >= n) break; pp += st[j]; // Adding to set z.insert(pp); } } // Converting set into a list vector<string> fin(z.begin(), z.end()); // Sorting the strings int the list // into lexicographical order sort(fin.begin(), fin.end()); // Printing kth substring cout << fin[k - 1];}// Driver codeint main(){ string s = "neveropen"; int k = 5; int n = s.length(); kThLexString(s, k, n);}// This code is contributed by yatinagg |
Java
// Java implementation of // the above approach import java.util.*; class GFG{ public static void kThLexString(String st, int k, int n) { // Set to store the unique substring Set<String> z = new HashSet<String>(); for(int i = 0; i < n; i++) { // String to create each substring String pp = ""; for(int j = i; j < i + k; j++) { if (j >= n) break; pp += st.charAt(j); // Adding to set z.add(pp); } } // Converting set into a list Vector<String> fin = new Vector<String>(); fin.addAll(z); // Sorting the strings int the list // into lexicographical order Collections.sort(fin); // Printing kth substring System.out.print(fin.get(k - 1));} // Driver Codepublic static void main(String[] args) { String s = "neveropen"; int k = 5; int n = s.length(); kThLexString(s, k, n); }}// This code is contributed by divyeshrabadiya07 |
Python3
# Python3 implementation of the above approachdef kThLexString(st, k, n): # Set to store the unique substring z = set() for i in range(n): # String to create each substring pp = "" for j in range(i, i + k): if (j >= n): break pp += s[j] # adding to set z.add(pp) # converting set into a list fin = list(z) # sorting the strings int the list # into lexicographical order fin.sort() # printing kth substring print(fin[k - 1]) s = "neveropen"k = 5n = len(s)kThLexString(s, k, n) |
C#
// C# implementation of // the above approach using System; using System.Collections.Generic;using System.Collections;class GFG{ public static void kThLexString(string st, int k, int n) { // Set to store the unique substring HashSet<string> z = new HashSet<string>(); for(int i = 0; i < n; i++) { // String to create each substring string pp = ""; for(int j = i; j < i + k; j++) { if (j >= n) break; pp += st[j]; // Adding to set z.Add(pp); } } // Converting set into a list ArrayList fin = new ArrayList(); foreach(string s in z) { fin.Add(s); } // Sorting the strings int the list // into lexicographical order fin.Sort(); // Printing kth substring Console.Write(fin[k - 1]);} // Driver Codepublic static void Main(string[] args) { string s = "neveropen"; int k = 5; int n = s.Length; kThLexString(s, k, n); }}// This code is contributed by rutvik_56 |
Javascript
<script>// JavaScript implementation of the above approach function kThLexString(st, k, n){ // Set to store the unique substring var z = new Set(); for(var i = 0; i < n; i++) { // String to create each substring var pp = ""; for(var j = i; j < i + k; j++) { if (j >= n) break; pp += st[j]; // Adding to set z.add(pp); } } var fin = []; z.forEach(element => { fin.push(element); }); fin.sort(); // Printing kth substring document.write( fin[k-1]);}// Driver codevar s = "neveropen";var k = 5;var n = s.length;kThLexString(s, k, n);</script> |
eeksf
Time Complexity: O(nk log(nk) where n is the length of the string, and k is the length of the substring.
Space Complexity: O(nk)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!