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 codeint 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 codeif 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> |
Output
Yes
Time complexity : O(n)
Auxiliary Space : O(n)
This article is contributed by Himanshu Gupta(Bagri). If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
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!
