Given two strings a and b, the task is to check how many times the string a can be repeated to generate the string b. If b cannot be generated by repeating a then print -1.
Examples:
Input: a = “neveropen”, b = “neveropenneveropen”
Output: 2
“neveropen” can be repeated twice to generate “neveropenneveropen”Input: a = “df”, b = “dfgrt”
Output: -1
Approach:
- If len(b) % len(a) != 0 then print -1 as b cannot be generated by repeating a.
- Else set count = len(b) / len(a) and repeat a count number of times.
- If a = b then print count.
- Else print -1.
Below is the implementation of the above approach:
C++
// CPP implementation of the approach#include<bits/stdc++.h>using namespace std;// Function to return the count of repetitions // of string a to generate string bint getCount(string a, string b){ // If b cannot be generated by repeating a if(b.length() % a.length() != 0) return -1; int count = b.length() /a.length(); // Repeat a count number of times string str = ""; for(int i = 0; i < count; i++) { str = str + a; } if(str == b) return count; return -1; }// Driver codeint main(){ string a = "neveropen"; string b = "neveropenneveropen"; cout << (getCount(a, b)); return 0;}// This code is contributed by// Surendra_Gangwar |
Java
// Java implementation of the approach class GfG{ // Function to return the count of repetitions // of string a to generate string b static int getCount(String a, String b) { // If b cannot be generated by repeating a if(b.length() % a.length() != 0) return -1; int count = b.length() / a.length(); // Repeat a count number of times String str = ""; for(int i = 0; i < count; i++) { str = str + a; } if(str.equals(b)) return count; return -1; } // Driver code public static void main(String []args) { String a = "neveropen"; String b = "neveropenneveropen"; System.out.println(getCount(a, b)); }} // This code is contributed by Rituraj Jain |
Python 3
# Python3 implementation of the approach# Function to return the count of repetitions # of string a to generate string bdef getCount(a, b): # If b cannot be generated by repeating a if(len(b) % len(a) != 0): return -1; count = int(len(b) / len(a)) # Repeat a count number of times a = a * count if(a == b): return count return -1;# Driver codeif __name__ == '__main__': a = 'neveropen' b = 'neveropenneveropen' print(getCount(a, b)) |
C#
// C# implementation of the approach using System;class GfG{ // Function to return the count of repetitions // of string a to generate string b static int getCount(String a, String b) { // If b cannot be generated by repeating a if(b.Length % a.Length != 0) return -1; int count = b.Length / a.Length; // Repeat a count number of times String str = ""; for(int i = 0; i < count; i++) { str = str + a; } if(str.Equals(b)) return count; return -1; } // Driver code public static void Main(String []args) { String a = "neveropen"; String b = "neveropenneveropen"; Console.WriteLine(getCount(a, b)); }}// This code contributed by Rajput-Ji |
Javascript
<script>// Javascript implementation of the approach // Function to return the count of repetitions // of string a to generate string b function getCount( a, b) { // If b cannot be generated by repeating a if (b.length % a.length != 0) return -1; var count = parseInt(b.length / a.length); // Repeat a count number of times var str = ""; for (i = 0; i < count; i++) { str = str + a; } if (str == (b)) return count; return -1; } // Driver code var a = "neveropen"; var b = "neveropenneveropen"; document.write(getCount(a, b));// This code is contributed by todaysgaurav </script> |
PHP
<?php// PHP implementation of the approach // Function to return the count of repetitions // of string a to generate string b function getCount($a, $b){ // If b cannot be generated by repeating a if(strlen($b) % strlen($a) != 0) return -1; $count = floor(strlen($b) / strlen($a)); // Repeat a count number of times // Repeat a count number of times $str = ""; for($i = 0; $i < $count; $i++) { $str = $str . $a ; } if(strcmp($a,$b)) return $count; return -1; }// Driver code $a = 'neveropen';$b = 'neveropenneveropen';echo getCount($a, $b); // This code is contributed by Ryuga?> |
Output
2
Time Complexity: O(n/m), where m and n are the lengths of the given strings a and b respectively.
Auxiliary Space: O(n), where n is the length of the string.
Approach:
- Check if the length of string b is a multiple of the length of string a. If not, return -1.
- Calculate the number of repetitions of a needed to generate b.
- Create an empty stack.
- Push each substring of length n (i.e., the length of a) from b onto the stack. This is done by iterating from 0 to the number of repetitions needed, and calling the substr() function on b with the starting index i*n and length n.
- Pop each substring from the stack and append it to a new string str. This is done by iterating until the stack is empty, calling the top() function to get the top element of the stack, concatenating it to str, and then calling the pop() function to remove the top element.
- Check if str is equal to b. If it is, return the number of repetitions calculated in step 2; otherwise, return -1.
Below is the implementation of the above approach:
C++
#include <iostream>#include <stack>using namespace std;int count_repetitions(string a, string b) { int n = a.length(); int m = b.length(); if (m % n != 0) { return -1; } int repetitions = m / n; stack<string> s; for (int i = 0; i < repetitions; i++) { s.push(b.substr(i*n, n)); } string str = ""; while (!s.empty()) { str += s.top(); s.pop(); } if (str == b) { return repetitions; } else { return -1; }}int main() { string a = "neveropen"; string b = "neveropenneveropen"; cout << count_repetitions(a, b) << endl; return 0;} |
Java
import java.util.*;public class Main { public static void main(String[] args) { String a = "neveropen"; String b = "neveropenneveropen"; System.out.println(countRepetitions(a, b)); } // Function to count the number of times string 'a' is repeated to form string 'b' public static int countRepetitions(String a, String b) { int n = a.length(); int m = b.length(); // If the length of string 'b' is not a multiple of the length of string 'a', it's not possible to repeat 'a' to form 'b' if (m % n != 0) { return -1; } // Calculate the number of repetitions required to form 'b' from 'a' int repetitions = m / n; // Use a stack to store the individual substrings of 'b' that correspond to each repetition of 'a' Stack<String> stack = new Stack<>(); for (int i = 0; i < repetitions; i++) { // Push each substring into the stack by extracting it from 'b' stack.push(b.substring(i * n, (i + 1) * n)); } // Build a new string by popping the substrings from the stack in reverse order StringBuilder str = new StringBuilder(); while (!stack.isEmpty()) { str.append(stack.pop()); } // If the final concatenated string matches 'b', it means 'a' is repeated 'repetitions' times to form 'b' // Return the number of repetitions, else return -1 if (str.toString().equals(b)) { return repetitions; } else { return -1; } }} |
Python3
def count_repetitions(a, b): n = len(a) m = len(b) # Check if the length of 'b' is a multiple of the length of 'a' if m % n != 0: return -1 repetitions = m // n stack = [] # Split 'b' into 'repetitions' parts and store them in the stack for i in range(repetitions): stack.append(b[i * n: (i + 1) * n]) str_result = "" # Pop elements from the stack and append them to 'str_result' while stack: str_result += stack.pop() # Compare 'str_result' with 'b' to check if they are the same if str_result == b: return repetitions else: return -1if __name__ == "__main__": a = "neveropen" b = "neveropenneveropen" print(count_repetitions(a, b))# This code is contributed by shivamgupta0987654321 |
C#
using System;public class GFG{ // Function to count repetitions of 'a' in 'b' public static int CountRepetitions(string a, string b) { int n = a.Length; int m = b.Length; // Check if the length of 'b' is a multiple of the length of 'a' if (m % n != 0) { return -1; } int repetitions = m / n; var stack = new System.Collections.Generic.Stack<string>(); // Split 'b' into 'repetitions' parts and store them in the stack for (int i = 0; i < repetitions; i++) { stack.Push(b.Substring(i * n, n)); } string strResult = ""; // Pop elements from the stack and append them to 'strResult' while (stack.Count > 0) { strResult += stack.Pop(); } // Compare 'strResult' with 'b' to check if they are the same if (strResult == b) { return repetitions; } else { return -1; } } public static void Main(string[] args) { string a = "neveropen"; string b = "neveropenneveropen"; Console.WriteLine(CountRepetitions(a, b)); }}// This code is contributed by rambabuguphka |
Javascript
function countRepetitions(a, b) { const n = a.length; const m = b.length; // Check if the length of 'b' is a multiple of the length of 'a' if (m % n !== 0) { return -1; } const repetitions = m / n; const stack = []; // Split 'b' into 'repetitions' parts and store them in the stack for (let i = 0; i < repetitions; i++) { stack.push(b.substring(i * n, (i + 1) * n)); } let strResult = ""; // Pop elements from the stack and append them to 'strResult' while (stack.length > 0) { strResult += stack.pop(); } // Compare 'strResult' with 'b' to check if they are the same if (strResult === b) { return repetitions; } else { return -1; }}const a = "neveropen";const b = "neveropenneveropen";console.log(countRepetitions(a, b));// This code is contributed by shivamgupta0987654321 |
Output
2
Time Complexity: O(m), where m is the length of the string b.
Auxiliary Space: O(m/n + m), where n is the length of the string a and m is the length of the string b.
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!
