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 stringstring 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 codeint 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 stringdef 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 codeif __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);}// Testlet s = "abababa";let k = 2;// Function callconsole.log(kPeriodic(s, k)); |
-1
Time Complexity: O(n*log n)
Auxilairy 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!
