Check if concatenation of splitted substrings of two given strings forms a palindrome or not
Given two strings a and b of the same length, the task is to check if splitting both the strings and concatenating their opposite substrings, i.e. concatenating the left substring of a with right substring of b or concatenating the left substring of b with right substring of a, forms a palindrome or not. If found to be true print “Yes”. Otherwise, print “No”.
Note: One of the splitted substrings can be empty.
Examples:
Input: a = “x”, b = “y”
Output: Yes
Explanation:
Split both the strings at index 0.
Left substring of a (aLeft) = ” “, Right substring of a (aRight) = “x”
Left substring of b (bLeft) = ” “, Right substring of b (bRight) = “y”
Since aLeft + bRight = ” ” + “y” = “y”, which is a palindrome as well as bLeft + aRight= ” ” + “x” = “x” is also a palindrome, print Yes.Input: a = “ulacfd”, b = “jizalu”
Output: True
Explanation:
Split both the strings at index 3:
Left substring of a (aLeft) = “ula”, Right substring of a (aRight) = “cfd”
, Left substring of b (bLeft) = “jiz”, Right substring of b (bRight) = “alu”
Since aleft + bright = “ula” + “alu” = “ulaalu”, which is a palindrome, print Yes.
Approach: The idea is to use Two Pointer technique to solve this problem. Follow the steps below to solve the problem:
- Place a pointer i at 0th index of a and “j” at the last index of b.
- Iterate over the characters of the string and check if a[i] == b[j], then increment i and decrement j.
- Otherwise, just break the loop as its not a palindrome type sequence.
- Concatenate aLeft and bRight in a string variable xa and aRight and bLeft in another string variable xb.
- Check if either of the two strings is a palindrome or not. If found to be true, print “Yes”. Otherwise, print “No”.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to check if concatenating // opposite substrings after splitting // two given strings forms a palindrome // or not bool checkSplitting(string a, string b) { // Length of the string int len = a.length(); int i = 0, j = len - 1; // Iterate through the strings while (i < len) { // If not a palindrome sequence if (a[i] != b[j]) { break ; } i += 1; j -= 1; // Concatenate left substring of a // and right substring of b in xa // Concatenate right substring of a // and left substring of b in xb string xa = a.substr(i, j + 1); string xb = b.substr(i, j + 1); // Check if either of the two concatenated // strings is a palindrome or not if (xa == string(xa.rbegin(), xa.rend()) || xb == string(xb.rbegin(), xb.rend())) return true ; } } // Function to check if concatenation of splitted // substrings of two given strings forms a palindrome void isSplitPossible(string a, string b) { if (checkSplitting(a, b) == true ) { cout << "Yes" ; } else if (checkSplitting(b, a) == true ) { cout << "Yes" ; } else { cout << "No" ; } } // Driver Code int main() { string a = "ulacfd" , b = "jizalu" ; // Function Call isSplitPossible(a, b); return 0; } // This code is contributed by pushpendrayadav1057 |
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to check if concatenating // opposite subStrings after splitting // two given Strings forms a palindrome // or not static boolean checkSplitting(String a, String b) { // Length of the String int len = a.length(); int i = 0 , j = len - 1 ; // Iterate through the Strings while (i < len) { // If not a palindrome sequence if (a.charAt(i) != b.charAt(j)) { break ; } i += 1 ; j -= 1 ; // Concatenate left subString of a // and right subString of b in xa // Concatenate right subString of a // and left subString of b in xb String xa = a.substring(i, j + 1 ); String xb = b.substring(i, j + 1 ); // Check if either of the two concatenated // Strings is a palindrome or not if (xa.equals(reverse(xa))||xb.equals(reverse(xb))) return true ; } return false ; } // Function to check if concatenation of splitted // subStrings of two given Strings forms a palindrome static void isSplitPossible(String a, String b) { if (checkSplitting(a, b) == true ) { System.out.print( "Yes" ); } else if (checkSplitting(b, a) == true ) { System.out.print( "Yes" ); } else { System.out.print( "No" ); } } static String reverse(String input) { char [] a = input.toCharArray(); int l, r = a.length - 1 ; for (l = 0 ; l < r; l++, r--) { char temp = a[l]; a[l] = a[r]; a[r] = temp; } return String.valueOf(a); } // Driver Code public static void main(String[] args) { String a = "ulacfd" , b = "jizalu" ; // Function Call isSplitPossible(a, b); } } // This code is contributed by 29AjayKumar |
Python3
# Python3 program for the above approach # Function to check if concatenating # opposite substrings after splitting # two given strings forms a palindrome or not def checkSplitting(a, b, n): i, j = 0 , n - 1 # Iterate through the strings while (i < n): # If not a palindrome sequence if (a[i] ! = b[j]): break i + = 1 j - = 1 # Concatenate left substring of a # and right substring of b in xa # Concatenate right substring of a # and left substring of b in xb xa = a[i:j + 1 ] xb = b[i:j + 1 ] # Check if either of the two concatenated # strings is a palindrome or not if (xa = = xa[:: - 1 ] or xb = = xb[:: - 1 ]): return True # Function to check if concatenation of splitted # substrings of two given strings forms a palindrome def isSplitPossible(a, b): if checkSplitting(a, b, len (a)) = = True : print ( "Yes" ) elif checkSplitting(b, a, len (a)) = = True : print ( "Yes" ) else : print ( "No" ) # Given string a and b a = "ulacfd" b = "jizalu" # Function Call isSplitPossible(a, b) |
C#
// C# program for the above approach using System; class GFG{ // Function to check if concatenating // opposite subStrings after splitting // two given Strings forms a palindrome // or not static bool checkSplitting(String a, String b) { // Length of the String int len = a.Length; int i = 0, j = len - 1; // Iterate through the Strings while (i < len) { // If not a palindrome sequence if (a[i] != b[j]) { break ; } i += 1; j -= 1; // Concatenate left subString of a // and right subString of b in xa // Concatenate right subString of a // and left subString of b in xb String xa = a.Substring(i, j + 1 - i); String xb = b.Substring(i, j + 1 - i); // Check if either of the two concatenated // Strings is a palindrome or not if (xa.Equals(reverse(xa)) || xb.Equals(reverse(xb))) return true ; } return false ; } // Function to check if concatenation of splitted // subStrings of two given Strings forms a palindrome static void isSplitPossible(String a, String b) { if (checkSplitting(a, b) == true ) { Console.Write( "Yes" ); } else if (checkSplitting(b, a) == true ) { Console.Write( "Yes" ); } else { Console.Write( "No" ); } } static String reverse(String input) { char [] a = input.ToCharArray(); int l, r = a.Length - 1; for (l = 0; l < r; l++, r--) { char temp = a[l]; a[l] = a[r]; a[r] = temp; } return String.Join( "" ,a); } // Driver Code public static void Main(String[] args) { String a = "ulacfd" , b = "jizalu" ; // Function Call isSplitPossible(a, b); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // JavaScript program for the above approach // Function to check if the string is palindrome or not function checkPalindrome(str) { // find the length of a string var len = str.length; // loop through half of the string for ( var i = 0; i < parseInt(len / 2); i++) { // check if first and last string are same if (str[i] !== str[len - 1 - i]) { return false ; } } return true ; } // Function to check if concatenating // opposite substrings after splitting // two given strings forms a palindrome // or not function checkSplitting(a, b) { // Length of the string var len = a.length; var i = 0, j = len - 1; // Iterate through the strings while (i < len) { // If not a palindrome sequence if (a[i] != b[j]) { break ; } i += 1; j -= 1; // Concatenate left substring of a // and right substring of b in xa // Concatenate right substring of a // and left substring of b in xb var xa = a.substring(i, j + 1); var xb = b.substring(i, j + 1); // Check if either of the two concatenated // strings is a palindrome or not if (checkPalindrome(xa)== true || checkPalindrome(xb)== true ) return true ; } } // Function to check if concatenation of splitted // substrings of two given strings forms a palindrome function isSplitPossible(a, b) { if (checkSplitting(a, b) == true ) { document.write( "Yes" ); } else if (checkSplitting(b, a) == true ) { document.write( "Yes" ); } else { document.write( "No" ); } } var a = "ulacfd" , b = "jizalu" ; // Function Call isSplitPossible(a, b); // This code is contributed by SoumikMondal </script> |
Yes
Time Complexity: O(N)
Auxiliary Space: O(1)
Contact Us