Convert to a string that is repetition of a substring of k length
Given a string, find if it is possible to convert it to a string that is the repetition of a substring with k characters. To convert, we can replace one substring of length k starting at index i (zero-based indexing) such that i is divisible by K, with k characters.
Examples:
Input: str = "bdac", k = 2 Output: True We can either replace "bd" with "ac" or "ac" with "bd". Input: str = "abcbedabcabc", k = 3 Output: True Replace "bed" with "abc" so that the whole string becomes repetition of "abc". Input: str = "bcacc", k = 3 Output: False k doesn't divide string length i.e. 5%3 != 0 Input: str = "bcacbcac", k = 2 Output: False Input: str = "bcdbcdabcedcbcd", k = 3 Output: False
This can be used in compression. If we have a string where the complete string is repetition except one substring, then we can use this algorithm to compress the string.
One observation is, length of string must be a multiple of k as we can replace only one substring.
The idea is to declare a map mp which maps strings of length k to an integer denoting its count. So, if there are only two different sub-strings of length k in the map container and the count of one of the sub-string is 1 then the answer is true. Otherwise, answer is false.
Implementation:
C++
// C++ program to check if a string can be converted to // a string that has repeated substrings of length k. #include<bits/stdc++.h> using namespace std; // Returns true if str can be converted to a string // with k repeated substrings after replacing k // characters. bool checkString(string str, long k) { // Length of string must be a multiple of k int n = str.length(); if (n%k != 0) return false ; // Map to store strings of length k and their counts unordered_map<string, int > mp; for ( int i=0; i<n; i+=k) mp[str.substr(i, k)]++; // If string is already a repetition of k substrings, // return true. if (mp.size() == 1) return true ; // If number of distinct substrings is not 2, then // not possible to replace a string. if (mp.size() != 2) return false ; // One of the two distinct must appear exactly once. // Either the first entry appears once, or it appears // n/k-1 times to make other substring appear once. if ((mp.begin()->second == (n/k - 1)) || mp.begin()->second == 1) return true ; return false ; } // Driver code int main() { checkString( "abababcd" , 2)? cout << "Yes" : cout << "No" ; return 0; } |
Java
// Java program to check if a string // can be converted to a string that has // repeated substrings of length k. import java.util.HashMap; import java.util.Iterator; class GFG { // Returns true if str can be converted // to a string with k repeated substrings // after replacing k characters. static boolean checkString(String str, int k) { // Length of string must be // a multiple of k int n = str.length(); if (n % k != 0 ) return false ; // Map to store strings of // length k and their counts HashMap<String, Integer> mp = new HashMap<>(); try { for ( int i = 0 ; i < n; i += k) mp.put(str.substring(i, k), mp.get(str.substring(i, k)) == null ? 1 : mp.get(str.substring(i, k)) + 1 ); } catch (Exception e) { } // If string is already a repetition // of k substrings, return true. if (mp.size() == 1 ) return true ; // If number of distinct substrings is not 2, // then not possible to replace a string. if (mp.size() != 2 ) return false ; HashMap.Entry<String, Integer> entry = mp.entrySet().iterator().next(); // One of the two distinct must appear // exactly once. Either the first entry // appears once, or it appears n/k-1 times // to make other substring appear once. if (entry.getValue() == (n / k - 1 ) || entry.getValue() == 1 ) return true ; return false ; } // Driver code public static void main(String[] args) { if (checkString( "abababcd" , 2 )) System.out.println( "Yes" ); else System.out.println( "No" ); } } // This code is contributed by // sanjeev2552 |
Python3
# Python3 program to check if a can be converted to # a that has repeated subs of length k. # Returns True if S can be converted to a # with k repeated subs after replacing k # characters. def check( S, k): # Length of must be a multiple of k n = len (S) if (n % k ! = 0 ): return False # Map to store s of length k and their counts mp = {} for i in range ( 0 , n, k): mp[S[i:k]] = mp.get(S[i:k], 0 ) + 1 # If is already a repetition of k subs, # return True. if ( len (mp) = = 1 ): return True # If number of distinct subs is not 2, then # not possible to replace a . if ( len (mp) ! = 2 ): return False # One of the two distinct must appear exactly once. # Either the first entry appears once, or it appears # n/k-1 times to make other sub appear once. for i in mp: if i = = (n / / k - 1 ) or mp[i] = = 1 : return True return False # Driver code if check( "abababcd" , 2 ): print ( "Yes" ) else : print ( "No" ) # This code is contributed by mohit kumar 29 |
C#
// C# program to check if a string // can be converted to a string that has // repeated substrings of length k. using System; using System.Collections.Generic; class GFG { // Returns true if str can be converted // to a string with k repeated substrings // after replacing k characters. static bool checkString(String str, int k) { // Length of string must be // a multiple of k int n = str.Length; if (n % k != 0) return false ; // Map to store strings of // length k and their counts Dictionary<String, int > mp = new Dictionary<String, int >(); for ( int i = 0; i < n; i += k) { if (!mp.ContainsKey(str.Substring(i, k))) mp.Add(str.Substring(i, k), 1); else mp[str.Substring(i, k)] = mp[str.Substring(i, k)] + 1; } // If string is already a repetition // of k substrings, return true. if (mp.Count == 1) return true ; // If number of distinct substrings is not 2, // then not possible to replace a string. if (mp.Count != 2) return false ; foreach (KeyValuePair<String, int > entry in mp) { // One of the two distinct must appear // exactly once. Either the first entry // appears once, or it appears n/k-1 times // to make other substring appear once. if (entry.Value == (n / k - 1) || entry.Value == 1) return true ; } return false ; } // Driver code public static void Main(String[] args) { if (checkString( "abababcd" , 2)) Console.WriteLine( "Yes" ); else Console.WriteLine( "No" ); } } // This code is contributed by Princi Singh |
Javascript
<script> // Javascript program to check if a string // can be converted to a string that has // repeated substrings of length k. // Returns true if str can be converted // to a string with k repeated substrings // after replacing k characters. function checkString(str,k) { // Length of string must be // a multiple of k let n = str.length; if (n % k != 0) return false ; // Map to store strings of // length k and their counts let mp = new Map(); for (let i = 0; i < n; i += k) { if (mp.has(str.substring(i, i+k))) mp.set(str.substring(i, i+k),mp.get(str.substring(i, i+k)) + 1); else mp.set(str.substring(i, i+k),1); } // If string is already a repetition // of k substrings, return true. if (mp.size == 1) return true ; // If number of distinct substrings is not 2, // then not possible to replace a string. if (mp.size != 2) { return false ; } // One of the two distinct must appear // exactly once. Either the first entry // appears once, or it appears n/k-1 times // to make other substring appear once. for (let [key, value] of mp.entries()) { if (value == (Math.floor(n/k) - 1) || value == 1) return true ; } return false ; } // Driver code if (checkString( "abababcd" , 2)) document.write( "Yes" ); else document.write( "No" ); // This code is contributed by unknown2108 </script> |
Yes
Time complexity : O(n)
Auxiliary Space : O(n)