Find Lexicographically smallest String
Given a circular string s, find whether there exists a permutation of s which is a K-periodic circular string and if it exists then find the lexicographically smallest permutation of s which is a K-periodic circular string. Return an empty string if there does not exist a valid permutation of s which is a K-periodic circular string.
Note: You can rotate the string in any direction. A K-periodic circular string is a circular string that remains the same when it is rotated by K units.
Examples:
Input: s = “abba”, K = 2
Output: abab
Explanation: “abab” when rotated by 2 units remains the same.Input: s = “abbbbbb”, K = 4
Output: -1
Explanation: No permutation of s can be a 4-periodic circular string.
Approach: This can be solved with the following idea:
By keeping in mind, for each of the character at ith index, i == (i + k) % n == (i + 2 * k) % n == (i + 3 * k) % n, … should be same.
Below are the steps involved:
- Intialise a map mp
- Store frequency of each character in mp.
- intialize a req by n/ gcd(n,k).
- Iterate in map,
- For each frequency, we need to add that particular character in f upto frequency/req.
- For req time we need to add f in ans, which will be our required string.
Below is the implementation of the code:
C++
// C++ code for the above approach: #include <bits/stdc++.h> #include <iostream> using namespace std; // Function to find lexographically // smallest string string kPeriodic(string s, int k) { map< char , int > mp; // Store the frequency of each element for ( int i = 0; i < s.size(); i++) mp[s[i]]++; int n = s.size(); int req = n / __gcd(n, k); // If the string cannot be formed for ( auto t : mp) if (t.second % req) return "-1"; string f = ""; // Iterate in map for ( auto t : mp) { int fre = t.second / req; while (fre--) f += t.first; } // String will be returned string ans = ""; while (req--) ans += f; // Return the final string return ans; } // Driver code int main() { string s = "abababa"; int k = 2; // Function call cout << kPeriodic(s, k); return 0; } |
Java
import java.util.HashMap; import java.util.Map; public class LexicographicallySmallestString { public static String kPeriodic(String s, int k) { Map<Character, Integer> mp = new HashMap<>(); // Store the frequency of each element for ( int i = 0 ; i < s.length(); i++) { char ch = s.charAt(i); mp.put(ch, mp.getOrDefault(ch, 0 ) + 1 ); } int n = s.length(); int gcd = gcd(n, k); int req = n / gcd; // If the string cannot be formed for (Map.Entry<Character, Integer> entry : mp.entrySet()) { if (entry.getValue() % req != 0 ) { return "-1" ; } } StringBuilder f = new StringBuilder(); // Iterate in map for (Map.Entry<Character, Integer> entry : mp.entrySet()) { int fre = entry.getValue() / req; for ( int i = 0 ; i < fre; i++) { f.append(entry.getKey()); } } // String will be returned StringBuilder ans = new StringBuilder(); for ( int i = 0 ; i < req; i++) { ans.append(f); } // Return the final string return ans.toString(); } public static int gcd( int a, int b) { if (b == 0 ) { return a; } return gcd(b, a % b); } public static void main(String[] args) { String s = "abababa" ; int k = 2 ; // Function call System.out.println(kPeriodic(s, k)); } } |
Python3
import math # Function to find lexicographically # smallest string def k_periodic(s, k): mp = {} # Store the frequency of each element for i in range ( len (s)): if s[i] in mp: mp[s[i]] + = 1 else : mp[s[i]] = 1 n = len (s) req = n / / math.gcd(n, k) # If the string cannot be formed for t in mp.items(): if t[ 1 ] % req ! = 0 : return "-1" f = "" # Iterate in map for t in mp.items(): fre = t[ 1 ] / / req f + = t[ 0 ] * fre # String will be returned ans = "" for _ in range (req): ans + = f # Return the final string return ans # Driver code if __name__ = = "__main__" : s = "abababa" k = 2 # Function call print (k_periodic(s, k)) |
C#
using System; using System.Collections.Generic; class GFG { // Function to find lexographically smallest string static string KPeriodic( string s, int k) { Dictionary< char , int > mp = new Dictionary< char , int >(); // Store the frequency of the each element foreach ( char c in s) { if (mp.ContainsKey(c)) mp++; else mp = 1; } int n = s.Length; int req = n / GCD(n, k); // If the string cannot be formed foreach ( var t in mp) { if (t.Value % req != 0) return "-1" ; } string f = "" ; // Iterate in the dictionary foreach ( var t in mp) { int fre = t.Value / req; while (fre-- > 0) f += t.Key; } // String will be returned string ans = "" ; while (req-- > 0) ans += f; // Return the final string return ans; } // Function to find the Greatest Common Divisor (GCD) static int GCD( int a, int b) { while (b != 0) { int temp = b; b = a % b; a = temp; } return a; } // Driver code static void Main() { string s = "abababa" ; int k = 2; // Function call Console.WriteLine(KPeriodic(s, k)); } } |
Javascript
function kPeriodic(s, k) { let mp = new Map(); // Store the frequency of each element for (let i = 0; i < s.length; i++) { let ch = s.charAt(i); mp.set(ch, (mp.get(ch) || 0) + 1); } let n = s.length; let gcd = calculateGCD(n, k); let req = n / gcd; // If the string cannot be formed for (let [key, value] of mp.entries()) { if (value % req !== 0) { return "-1" ; } } let f = "" ; // Iterate in map for (let [key, value] of mp.entries()) { let fre = value / req; for (let i = 0; i < fre; i++) { f += key; } } // String will be returned let ans = "" ; for (let i = 0; i < req; i++) { ans += f; } // Return the final string return ans; } function calculateGCD(a, b) { if (b === 0) { return a; } return calculateGCD(b, a % b); } // Test let s = "abababa" ; let k = 2; // Function call console.log(kPeriodic(s, k)); |
-1
Time Complexity: O(n*log n)
Auxilairy Space: O(n)