Given two strings S1 and S2, which consists of uppercase alphabets. Find the shortest string str which consists of # and uppercase letters, where the number of # must be less than the number of letters. Make sure if you replace the # in the string str with any string of uppercase letters of any length (possibly empty), then it must match string S1 and string S2. If it is possible to find such a string then print the string, otherwise print -1.
Note: If multiple answers are possible then print any.
Examples:
Input: S1= “GEEKSFORGEEKS” , S2= “FOR”
Output: str = “#FOR#”
Explanation : we can replace the first # with “GEEKS” and last # with “GEEKS” then it satisfies for the string S1. and then if you replace the first # with an empty string and second # with an empty string it satisfies the string S2.Input: S1 =”GEEKS” , S2= “GEEK”
Output: str = “G#”
Explanation : we can replace the first # with “EEKS” then it satisfies for the string S1. and then if you replace the first # with “EEK” it satisfies the string S2.Input: S1=”CODE”, S2= “GEEKS”
Output: -1
Explanation: we can’t use “#E#” because it has more # than uppercase letters.
Approach: To solve the problem follow the below idea:
We have to check if there is any common substring in two string, if NO, then just print -1, otherwise we have to find the longest common substring between two string and then we have to check the length of that string.
- Case 1: If the first character of two string is same then print that character and after that print a #.
- Case 2: If the last character of two string is same then first print the # then print the last character.
- Case 3: If the common substring is in the middle position of any string then check the length, if the length is less than 2 then just print -1, because we can’t use two # and one uppercase letters as the number of # must be less than the number of letters in our output string, otherwise print the common substring with two #, one is at first and another at last.
Below are the steps for the above approach:
- Check the longest common substring between two strings.
- If there is no common substring, print -1.
- Else, check if the first character of the two strings is the same then print that character, and after that print a “#”.
- If S1[S1.size() – 1] == S2[S2.size() – 1], print a “#” and S1[S1.size() – 1].
- If the last character of the two strings is the same then first print “#” and then print the last character.
- If S1[0] == S2[0], print S1[0] and a “#”.
- Otherwise, check the length of the common substring.
- If the length is greater than or equal to 2, print the common substring with two “#”, one is at first and another at last.
- Print a “#”, then print the substring and then print a “#”.
- If the length is less than 2 then print -1.
C++
// code to implement the above approach#include <bits/stdc++.h>using namespace std;// Function to find longest// common substring.string LCSubStr(string S1, string S2){ // Find length of both the strings int m = S1.length(); int n = S2.length(); // Variable to store length of // longest common substring. int result = 0; // Variable to store ending point of // longest common substring in X. int end; // Matrix to store result of two // consecutive rows at a time. int len[2][n + 1]; // Variable to represent which row of // matrix is current row. int currRow = 0; // For a particular value of i and j, // len[currRow][j] stores length of // longest common substring in // string X[0..i] and Y[0..j]. for (int i = 0; i <= m; i++) { for (int j = 0; j <= n; j++) { if (i == 0 || j == 0) { len[currRow][j] = 0; } else if (S1[i - 1] == S2[j - 1]) { len[currRow][j] = len[1 - currRow][j - 1] + 1; if (len[currRow][j] > result) { result = len[currRow][j]; end = i - 1; } } else { len[currRow][j] = 0; } } // Make current row as previous // row and previous row as // new current row. currRow = 1 - currRow; } // If there is no common substring, // print -1. if (result == 0) { return "-1"; } // Longest common substring is from // index end - result + 1 to // index end in X. return S1.substr(end - result + 1, result);}// Function to find the Output stringvoid ShortenMatch(string S1, string S2){ // Check if there is a common substring // between S1 and S2 If NO // then print -1 if (LCSubStr(S1, S2) == "-1") { cout << -1 << endl; } // If yes then check the cases else { // If last character of two string // are same then print # and // then the last character if (S1[S1.size() - 1] == S2[S2.size() - 1]) { cout << "#" << S1[S1.size() - 1] << endl; } // If first character of two // string are same then print // the last character and then # else if (S1[0] == S2[0]) { cout << S1[0] << "#" << endl; } // Otherwise check the // common substring else { string str = LCSubStr(S1, S2); // If the length of common // substring is more than 1 // then print the substring with // two #s, one is at first // and another is at last. if (str.length() >= 2) { cout << "#" << str << "#" << endl; } // Otherwise print -1 else { cout << -1 << endl; } } }}// Driver Codeint main(){ string S1 = "FOR"; string S2 = "GEEKSFORGEEKS"; // Function Call ShortenMatch(S1, S2); return 0;} |
Java
import java.io.*;import java.lang.*;public class GFG{ // Function to find longest common substring public static String LCSubStr(String S1, String S2) { // Find length of both the strings int m = S1.length(); int n = S2.length(); // Variable to store length of longest common substring. int result = 0; // Variable to store ending point of longest common substring in X. int end = 0; // Matrix to store result of two consecutive rows at a time. int[][] len = new int[2][n + 1]; // Variable to represent which row of matrix is current row. int currRow = 0; // For a particular value of i and j, // len[currRow][j] stores length of longest common substring // in string X[0..i] and Y[0..j]. for (int i = 0; i <= m; i++) { for (int j = 0; j <= n; j++) { if (i == 0 || j == 0) { len[currRow][j] = 0; } else if (S1.charAt(i - 1) == S2.charAt(j - 1)) { len[currRow][j] = len[1 - currRow][j - 1] + 1; if (len[currRow][j] > result) { result = len[currRow][j]; end = i - 1; } } else { len[currRow][j] = 0; } } // Make current row as previous row and previous row as new current row. currRow = 1 - currRow; } // If there is no common substring, return "-1". if (result == 0) { return "-1"; } // Longest common substring is from index end - result + 1 to index end in X. return S1.substring(end - result + 1, end + 1); } // Function to find the output string public static void main(String[] args) { String S1="GEEKSFORGEEKS"; String S2="FOR"; // Check if there is a common substring between S1 and S2 // If no, then print -1. if (LCSubStr(S1, S2).equals("-1")) { System.out.println(-1); } // If yes, then check the cases. else { // If last character of two strings are same, then print "#" and // then the last character. if (S1.charAt(S1.length() - 1) == S2.charAt(S2.length() - 1)) { System.out.println("#" + S1.charAt(S1.length() - 1)); } // If first character of two strings are same, then print // the last character and then "#". else if (S1.charAt(0) == S2.charAt(0)) { System.out.println(S1.charAt(0) + "#"); } // Otherwise check the common substring. else { String str = LCSubStr(S1, S2); // If the length of common substring is more than 1, // then print the substring with two "#"s, one is at first // and another is at last. if (str.length() >= 2) { System.out.println("#"+str+"#"); } else System.out.println(-1); } } }} |
Python3
# Python3 code to implement the above approach# Function to find longest# common substring.def LCSubStr(S1, S2): # Find length of both the strings m = len(S1) n = len(S2) # Variable to store length of # longest common substring. result = 0 # Variable to store ending point of # longest common substring in X. end = 0 # Matrix to store result of two # consecutive rows at a time. length = [[0] * (n + 1) for i in range(2)] # Variable to represent which row of # matrix is current row. currRow = 0 # For a particular value of i and j, # len[currRow][j] stores length of # longest common substring in # string X[0..i] and Y[0..j]. for i in range(m + 1): for j in range(n + 1): if i == 0 or j == 0: length[currRow][j] = 0 elif S1[i - 1] == S2[j - 1]: length[currRow][j] = length[1 - currRow][j - 1] + 1 if length[currRow][j] > result: result = length[currRow][j] end = i - 1 else: length[currRow][j] = 0 # Make current row as previous # row and previous row as # new current row. currRow = 1 - currRow # If there is no common substring, # print -1. if result == 0: return "-1" # Longest common substring is from # index end - result + 1 to # index end in X. return S1[end - result + 1:end + 1]# Function to find the Output stringdef ShortenMatch(S1, S2): # Check if there is a common substring # between S1 and S2 If NO # then print -1 if LCSubStr(S1, S2) == "-1": print(-1) # If yes then check the cases else: # If last character of two string # are same then print # and # then the last character if S1[-1] == S2[-1]: print("#" + S1[-1]) # If first character of two # string are same then print # the last character and then # elif S1[0] == S2[0]: print(S1[0] + "#") # Otherwise check the # common substring else: str = LCSubStr(S1, S2) # If the length of common # substring is more than 1 # then print the substring with # two #s, one is at first # and another is at last. if len(str) >= 2: print("#" + str + "#") # Otherwise print -1 else: print(-1)# Driver Codeif __name__ == "__main__": S1 = "FOR" S2 = "GEEKSFORGEEKS" # Function Call ShortenMatch(S1, S2) |
C#
using System;public class Program { // Function to find longest // common substring. public static string LCSubStr(string S1, string S2) { // Find length of both the strings int m = S1.Length; int n = S2.Length; // Variable to store length of // longest common substring. int result = 0; // Variable to store ending point of // longest common substring in X. int end = 0; // Matrix to store result of two // consecutive rows at a time. int[, ] len = new int[2, n + 1]; // Variable to represent which row of // matrix is current row. int currRow = 0; // For a particular value of i and j, // len[currRow,j] stores length of // longest common substring in // string X[0..i] and Y[0..j]. for (int i = 0; i <= m; i++) { for (int j = 0; j <= n; j++) { if (i == 0 || j == 0) { len[currRow, j] = 0; } else if (S1[i - 1] == S2[j - 1]) { len[currRow, j] = len[1 - currRow, j - 1] + 1; if (len[currRow, j] > result) { result = len[currRow, j]; end = i - 1; } } else { len[currRow, j] = 0; } } // Make current row as previous // row and previous row as // new current row. currRow = 1 - currRow; } // If there is no common substring, // return "-1". if (result == 0) { return "-1"; } // Longest common substring is from // index end - result + 1 to // index end in X. return S1.Substring(end - result + 1, result); } // Function to find the Output string public static void ShortenMatch(string S1, string S2) { // Check if there is a common substring // between S1 and S2 If NO // then print -1 if (LCSubStr(S1, S2) == "-1") { Console.WriteLine("-1"); } // If yes then check the cases else { // If last character of two string // are same then print # and // then the last character if (S1[S1.Length - 1] == S2[S2.Length - 1]) { Console.WriteLine("#" + S1[S1.Length - 1]); } // If first character of two // string are same then print // the last character and then # else if (S1[0] == S2[0]) { Console.WriteLine(S1[0] + "#"); } // Otherwise check the // common substring else { string str = LCSubStr(S1, S2); // If the length of common // substring is more than 1 // then print the substring with // two #s, one is at first // and another is at last. if (str.Length >= 2) { Console.Write("#"); Console.Write(str); Console.Write("#"); Console.Write("\n"); } // Otherwise print -1 else { Console.Write(-1); Console.Write("\n"); } } } } // Driver Code internal static void Main() { string S1 = "FOR"; string S2 = "GEEKSFORGEEKS"; // Function Call ShortenMatch(S1, S2); }} |
Javascript
function LCSubStr(S1, S2) { // Find length of both the strings let m = S1.length; let n = S2.length; // Variable to store length of // longest common substring. let result = 0; // Variable to store ending point of // longest common substring in X. let end; // Matrix to store result of two // consecutive rows at a time. let len = Array.from(Array(2), () => Array(n + 1).fill(0)); // Variable to represent which row of // matrix is current row. let currRow = 0; // For a particular value of i and j, // len[currRow][j] stores length of // longest common substring in // string X[0..i] and Y[0..j]. for (let i = 0; i <= m; i++) { for (let j = 0; j <= n; j++) { if (i == 0 || j == 0) { len[currRow][j] = 0; } else if (S1[i - 1] == S2[j - 1]) { len[currRow][j] = len[1 - currRow][j - 1] + 1; if (len[currRow][j] > result) { result = len[currRow][j]; end = i - 1; } } else { len[currRow][j] = 0; } } // Make current row as previous // row and previous row as // new current row. currRow = 1 - currRow; } // If there is no common substring, // print -1. if (result == 0) { return "-1"; } // Longest common substring is from // index end - result + 1 to // index end in X. return S1.substr(end - result + 1, result);}// Function to find the Output stringfunction ShortenMatch(S1, S2) { // Check if there is a common substring // between S1 and S2 If NO // then print -1 if (LCSubStr(S1, S2) == "-1") { console.log(-1); } // If yes then check the cases else { // If last character of two string // are same then print # and // then the last character if (S1[S1.length - 1] == S2[S2.length - 1]) { console.log("#" + S1[S1.length - 1]); } // If first character of two // string are same then print // the last character and then # else if (S1[0] == S2[0]) { console.log(S1[0] + "#"); } // Otherwise check the // common substring else { let str = LCSubStr(S1, S2); // If the length of common // substring is more than 1 // then print the substring with // two #s, one is at first // and another is at last. if (str.length >= 2) { console.log("#" + str + "#"); } // Otherwise print -1 else{ console.log(-1); } } }}// Driver Codelet S1 = "FOR";let S2 = "GEEKSFORGEEKS";// Function CallShortenMatch(S1, S2); |
Output
#FOR#
Time Complexity: O(n*m), where n and m are the lengths of two strings.
Auxiliary 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!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
