Given two strings str1 and str2 of lengths N and M respectively. The task is to find the least common multiple (LCM) of both the strings and if it doesn’t exist print -1.
Note: LCM of two strings is a string that can be formed by concatenating the strings to themselves and is shortest in length.
Examples:
Input: str1 = “baba”, str2 = “ba”
Output: baba
Explanation: “baba” is the smallest string that can be obtained from both str1 and str2.
Notice that “babababa” can be also be formed but the length of the string is not least.
Input: str1 = “aba”, str2 = “ab”
Output: -1
Explanation: No such string can be formed.
Approach: This problem is similar to finding shortest string formed by concatenating A x times and B y times. The task is solved by making lengths of both the strings equal and then checking whether both strings become the same or not. Follow the below steps to solve the problem:
- Iterate until the lengths of both strings are unequal.
- If the length of str1 is less than str2, append str1 to itself in else do the same for str2.
- After the loop, if both are equal, print any string, else print -1.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the lcm of both stringsstring findLcm(string str1, string str2){ string x = str1, y = str2; // While their length is unequal while (x.length() != y.length()) { if (x.length() < y.length()) x += str1; else y += str2; } if (x == y) return x; return "";}// Driver Codeint main(){ string str1 = "ba", str2 = "baba"; string ans = findLcm(str1, str2); if (ans != "") cout << ans; else { cout << -1; } return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{ // Function to find the lcm of both Strings static String findLcm(String str1, String str2) { String x = str1, y = str2; // While their length is unequal while (x.length() != y.length()) { if (x.length() < y.length()) x += str1; else y += str2; } if (x.equals(y)) return x; return ""; } // Driver Code public static void main(String[] args) { String str1 = "ba", str2 = "baba"; String ans = findLcm(str1, str2); if (ans != "") System.out.print(ans); else { System.out.print(-1); } }}// This code is contributed by shikhasingrajput |
Python3
# Python code for the above approach # Function to find the lcm of both stringsdef findLcm(str1, str2): x = str1 y = str2 # While their length is unequal while (len(x) != len(y)): if (len(x) < len(y)): x += str1; else: y += str2; if (x == y): return x; return "";# Driver Codestr1 = "ba"str2 = "baba"ans = findLcm(str1, str2)if (ans != ""): print(ans);else: print(-1);# This code is contributed by gfgking |
C#
// C# program for the above approachusing System;class GFG{ // Function to find the lcm of both strings static string findLcm(string str1, string str2) { string x = str1, y = str2; // While their length is unequal while (x.Length != y.Length) { if (x.Length < y.Length) x += str1; else y += str2; } if (x == y) return x; return ""; } // Driver Code public static void Main() { string str1 = "ba", str2 = "baba"; string ans = findLcm(str1, str2); if (ans != "") Console.Write(ans); else { Console.Write(-1); } }}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript code for the above approach // Function to find the lcm of both strings function findLcm(str1, str2) { let x = str1, y = str2; // While their length is unequal while (x.length != y.length) { if (x.length < y.length) x += str1; else y += str2; } if (x == y) return x; return ""; } // Driver Code let str1 = "ba", str2 = "baba"; let ans = findLcm(str1, str2); if (ans != "") document.write(ans); else { document.write(-1); } // This code is contributed by Potta Lokesh </script> |
baba
Time Complexity: O(N + M)
Auxiliary Space: O(N + M)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
