Given two strings A and B of length N, the task is to check if any of the two strings formed by splitting both the strings at any index i (0 ≤ i ≤ N – 1) and concatenating A[0, i] and B[i, N – 1] or A[i, N – 1] and B[0, i] respectively, form a palindromic string or not. If found to be true, print “Yes”. Otherwise, print “No”.
Examples:
Input: A = “x”, B = “y”
Output: Yes
Explanation:
Let the string be splitted at index 0 then,
Split A from index 0: “”+”x” A[0, 0] = “” and A[1, 1] = “x”.
Split B from index 0: “”+”y” B[0, 0] = “” and B[1, 1] = “y”.
The concatenation of A[0, 0] and B[1, 1] is = “y” which is a palindromic string.Input: A = “xbdef”, B = “xecab”
Output: No
Approach: The idea is to use the Two Pointer Technique and traverse the string over the range [0, N – 1] and check if the concatenation of substrings A[0, i – 1] and B[i, N – 1] or the concatenation of substrings A[i, N – 1] and B[0, i – 1] is a palindromic or not. If any of the concatenation is found to be palindromic then print “Yes” else print “No”.
Below is the implementation of the above approach:
C++
// C++ Program to implement // the above approach #include <bits/stdc++.h> using namespace std; // Function to check if a string // is palindrome or not bool isPalindrome(string str) { // Start and end of the // string int i = 0, j = str.size() - 1; // Iterate the string // until i > j while (i < j) { // If there is a mismatch if (str[i] != str[j]) return false ; // Increment first pointer // and decrement the other i++; j--; } // Given string is a // palindrome return true ; } // Function two check if // the strings can be // combined to form a palindrome void formPalindrome(string a, string b, int n) { // Initialize array of // characters char aa[n + 2]; char bb[n + 2]; for ( int i = 0; i < n + 2; i++) { aa[i] = ' ' ; bb[i] = ' ' ; } // Stores character of string // in the character array for ( int i = 1; i <= n; i++) { aa[i] = a[i - 1]; bb[i] = b[i - 1]; } bool ok = false ; for ( int i = 0; i <= n + 1; i++) { // Find left and right parts // of strings a and b string la = "" ; string ra = "" ; string lb = "" ; string rb = "" ; for ( int j = 1; j <= i - 1; j++) { // Substring a[j...i-1] if (aa[j] == ' ' ) la += "" ; else la += aa[j]; // Substring b[j...i-1] if (bb[j] == ' ' ) lb += "" ; else lb += bb[j]; } for ( int j = i; j <= n + 1; j++) { // Substring a[i...n] if (aa[j] == ' ' ) ra += "" ; else ra += aa[j]; // Substring b[i...n] if (bb[j] == ' ' ) rb += "" ; else rb += bb[j]; } // Check is left part of a + // right part of b or vice // versa is a palindrome if (isPalindrome(la + rb) || isPalindrome(lb + ra)) { ok = true ; break ; } } // Print the result if (ok) cout << ( "Yes" ); // Otherwise else cout << ( "No" ); } // Driver Code int main() { string A = "bdea" ; string B = "abbb" ; int N = 4; formPalindrome(A, B, N); } // This code is contributed by gauravrajput1 |
Java
// Java program for the above approach import java.io.*; import java.util.*; class GFG { // Function to check if a string // is palindrome or not static boolean isPalindrome(String str) { // Start and end of the string int i = 0 , j = str.length() - 1 ; // Iterate the string until i > j while (i < j) { // If there is a mismatch if (str.charAt(i) != str.charAt(j)) return false ; // Increment first pointer and // decrement the other i++; j--; } // Given string is a palindrome return true ; } // Function two check if the strings can // be combined to form a palindrome static void formPalindrome( String a, String b, int n) { // Initialize array of characters char aa[] = new char [n + 2 ]; char bb[] = new char [n + 2 ]; Arrays.fill(aa, ' ' ); Arrays.fill(bb, ' ' ); // Stores character of string // in the character array for ( int i = 1 ; i <= n; i++) { aa[i] = a.charAt(i - 1 ); bb[i] = b.charAt(i - 1 ); } boolean ok = false ; for ( int i = 0 ; i <= n + 1 ; i++) { // Find left and right parts // of strings a and b StringBuilder la = new StringBuilder(); StringBuilder ra = new StringBuilder(); StringBuilder lb = new StringBuilder(); StringBuilder rb = new StringBuilder(); for ( int j = 1 ; j <= i - 1 ; j++) { // Substring a[j...i-1] la.append((aa[j] == ' ' ) ? "" : aa[j]); // Substring b[j...i-1] lb.append((bb[j] == ' ' ) ? "" : bb[j]); } for ( int j = i; j <= n + 1 ; j++) { // Substring a[i...n] ra.append((aa[j] == ' ' ) ? "" : aa[j]); // Substring b[i...n] rb.append((bb[j] == ' ' ) ? "" : bb[j]); } // Check is left part of a + // right part of b or vice // versa is a palindrome if (isPalindrome(la.toString() + rb.toString()) || isPalindrome(lb.toString() + ra.toString())) { ok = true ; break ; } } // Print the result if (ok) System.out.println( "Yes" ); // Otherwise else System.out.println( "No" ); } // Driver Code public static void main(String[] args) { String A = "bdea" ; String B = "abbb" ; int N = 4 ; formPalindrome(A, B, N); } } |
Python3
# Python3 program for the # above approach # Function to check if # a string is palindrome # or not def isPalindrome(st): # Start and end of # the string i = 0 j = len (st) - 1 # Iterate the string # until i > j while (i < j): # If there is a mismatch if (st[i] ! = st[j]): return False # Increment first pointer # and decrement the other i + = 1 j - = 1 # Given string is a # palindrome return True # Function two check if # the strings can be # combined to form a # palindrome def formPalindrome(a, b, n): # Initialize array of # characters aa = [ ' ' ] * (n + 2 ) bb = [ ' ' ] * (n + 2 ) # Stores character of string # in the character array for i in range ( 1 , n + 1 ): aa[i] = a[i - 1 ] bb[i] = b[i - 1 ] ok = False for i in range (n + 2 ): # Find left and right parts # of strings a and b la = "" ra = "" lb = "" rb = "" for j in range ( 1 , i): # Substring a[j...i-1] if (aa[j] = = ' ' ): la + = "" else : la + = aa[j] # Substring b[j...i-1] if (bb[j] = = ' ' ): lb + = "" else : lb + = bb[j] for j in range (i, n + 2 ): # Substring a[i...n] if (aa[j] = = ' ' ): ra + = "" else : ra + = aa[j] # Substring b[i...n] if (bb[j] = = ' ' ): rb + = "" else : rb + = bb[j] # Check is left part of a + # right part of b or vice # versa is a palindrome if (isPalindrome( str (la) + str (rb)) or isPalindrome( str (lb) + str (ra))): ok = True break # Print the result if (ok): print ( "Yes" ) # Otherwise else : print ( "No" ) # Driver Code if __name__ = = "__main__" : A = "bdea" B = "abbb" N = 4 formPalindrome(A, B, N) # This code is contributed by Chitranayal |
C#
// C# program for the // above approach using System; using System.Text; class GFG{ // Function to check if a string // is palindrome or not static bool isPalindrome(String str) { // Start and end of the string int i = 0, j = str.Length - 1; // Iterate the string // until i > j while (i < j) { // If there is a mismatch if (str[i] != str[j]) return false ; // Increment first pointer // and decrement the other i++; j--; } // Given string is // a palindrome return true ; } // Function two check if the strings can // be combined to form a palindrome static void formPalindrome(String a, String b, int n) { // Initialize array of // characters char []aa = new char [n + 2]; char []bb = new char [n + 2]; for ( int i = 0; i < n + 2; i++) { aa[i] = ' ' ; bb[i] = ' ' ; } // Stores character of string // in the character array for ( int i = 1; i <= n; i++) { aa[i] = a[i-1]; bb[i] = b[i-1]; } bool ok = false ; for ( int i = 0; i <= n + 1; i++) { // Find left and right parts // of strings a and b StringBuilder la = new StringBuilder(); StringBuilder ra = new StringBuilder(); StringBuilder lb = new StringBuilder(); StringBuilder rb = new StringBuilder(); for ( int j = 1; j <= i - 1; j++) { // Substring a[j...i-1] la.Append((aa[j] == ' ' ) ? ' ' : aa[j]); // Substring b[j...i-1] lb.Append((bb[j] == ' ' ) ? ' ' : bb[j]); } for ( int j = i; j <= n + 1; j++) { // Substring a[i...n] ra.Append((aa[j] == ' ' ) ? ' ' : aa[j]); // Substring b[i...n] rb.Append((bb[j] == ' ' ) ? ' ' : bb[j]); } // Check is left part of a + // right part of b or vice // versa is a palindrome if (isPalindrome(la.ToString() + rb.ToString()) || isPalindrome(lb.ToString() + ra.ToString())) { ok = true ; break ; } } // Print the result if (!ok) Console.WriteLine( "Yes" ); // Otherwise else Console.WriteLine( "No" ); } // Driver Code public static void Main(String[] args) { String A = "bdea" ; String B = "abbb" ; int N = 4; formPalindrome(A, B, N); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // Javascript Program to implement // the above approach // Function to check if a string // is palindrome or not function isPalindrome(str) { // Start and end of the // string var i = 0, j = str.length - 1; // Iterate the string // until i > j while (i < j) { // If there is a mismatch if (str[i] != str[j]) return false ; // Increment first pointer // and decrement the other i++; j--; } // Given string is a // palindrome return true ; } // Function two check if // the strings can be // combined to form a palindrome function formPalindrome( a, b, n) { // Initialize array of // characters var aa= new Array(n + 2); var bb= new Array(n + 2); for ( var i = 0; i < n + 2; i++) { aa[i] = ' ' ; bb[i] = ' ' ; } // Stores character of string // in the character array for ( var i = 1; i <= n; i++) { aa[i] = a[i - 1]; bb[i] = b[i - 1]; } var ok = Boolean( false ); for ( var i = 0; i <= n + 1; i++) { // Find left and right parts // of strings a and b var la = "" ; var ra = "" ; var lb = "" ; var rb = "" ; for ( var j = 1; j <= i - 1; j++) { // Substring a[j...i-1] if (aa[j] == ' ' ) la += "" ; else la += aa[j]; // Substring b[j...i-1] if (bb[j] == ' ' ) lb += "" ; else lb += bb[j]; } for ( var j = i; j <= n + 1; j++) { // Substring a[i...n] if (aa[j] == ' ' ) ra += "" ; else ra += aa[j]; // Substring b[i...n] if (bb[j] == ' ' ) rb += "" ; else rb += bb[j]; } // Check is left part of a + // right part of b or vice // versa is a palindrome if (isPalindrome(la + rb) || isPalindrome(lb + ra)) { ok = true ; break ; } } // Print the result if (ok) document.write ( "Yes" ); // Otherwise else document.write ( "No" ); } var A = "bdea" ; var B = "abbb" ; var N = 4; formPalindrome(A, B, N); // This code is contributed by SoumikMondal </script> |
Yes
Time Complexity: O(N2) where N is the lengths of the given strings.
Auxiliary Space: O(N)
Alternate Python Approach(Two pointers +Slicing):
This approach follows the following path:
- Define the function check
- Take two pointers i,j at 0, n-1 position respectively
- If the first character of a and second character of b does not match we break (since we are searching for the palindrome)
- If matches we simply increment the pointer
- We would concatenate the form a[i:j+1] of the first string and b[i:j+1] of the second string and check for the condition of palindrome
- If yes we return True
C++
// C++ program to implement // the above approach #include<bits/stdc++.h> using namespace std; string rev(string str) { int st = 0; int ed = str.length() - 1; string s = str; while (st < ed) { swap(s[st], s[ed]); st++; ed--; } return s; } bool check(string a, string b, int n) { int i = 0; int j = n - 1; // iterate through the // length if we could // find a[i]==b[j] we could // increment I and decrement j while (i < n) { if (a[i] != b[j]) break ; // else we could just break // the loop as its not a // palindrome type sequence i += 1; j -= 1; // we could concatenate the // a's left part +b's right // part in a variable a and // a's right part+b's left // in the variable b string xa = a.substr(i, j + 1 - i); string xb = b.substr(i, j + 1 - i); // we would check for the // palindrome condition if // yes we print True else False if ((xa == rev(xa)) or (xb == rev(xb))) return true ; } return false ; } // Driver code int main() { string a = "xbdef" ; string b = "cabex" ; if (check(a, b, a.length()) == true or check(b, a, a.length()) == true ) cout << "True" ; else cout << "False" ; } // This code is contributed by Surendra_Gangwar |
Java
// Java program to implement // the above approach import java.util.*; import java.io.*; class GFG{ public static String rev(String str) { int st = 0 ; int ed = str.length() - 1 ; char [] s = str.toCharArray(); while (st < ed) { char temp = s[st]; s[st] = s[ed]; s[ed] = temp; st++; ed--; } return (s.toString()); } public static boolean check(String a, String b, int n) { int i = 0 ; int j = n - 1 ; // Iterate through the // length if we could // find a[i]==b[j] we could // increment I and decrement j while (i < n) { if (a.charAt(i) != b.charAt(j)) break ; // Else we could just break // the loop as its not a // palindrome type sequence i += 1 ; j -= 1 ; // We could concatenate the // a's left part +b's right // part in a variable a and // a's right part+b's left // in the variable b String xa = a.substring(i, j + 1 ); String xb = b.substring(i, j + 1 ); // We would check for the // palindrome condition if // yes we print True else False StringBuffer XA = new StringBuffer(xa); XA.reverse(); StringBuffer XB = new StringBuffer(xb); XB.reverse(); if (xa == XA.toString() || xb == XB.toString()) { return true ; } } return false ; } // Driver Code public static void main(String[] args) { String a = "xbdef" ; String b = "cabex" ; if (check(a, b, a.length()) || check(b, a, a.length())) System.out.println( "True" ); else System.out.println( "False" ); } } // This code is contributed by divyesh072019 |
Python3
# Python3 program to implement # the above approach def check(a, b, n): i, j = 0 , n - 1 # iterate through the length if # we could find a[i]==b[j] we could # increment I and decrement j while (i < n): if (a[i] ! = b[j]): # else we could just break # the loop as its not a palindrome # type sequence break i + = 1 j - = 1 # we could concatenate the a's left part # +b's right part in a variable a and a's # right part+b's left in the variable b xa = a[i:j + 1 ] xb = b[i:j + 1 ] # we would check for the palindrome condition # if yes we print True else False if (xa = = xa[:: - 1 ] or xb = = xb[:: - 1 ]): return True a = "xbdef" b = "cabex" if check(a, b, len (a)) = = True or check(b, a, len (a)) = = True : print ( True ) else : print ( False ) # CODE CONTRIBUTED BY SAIKUMAR KUDIKALA |
C#
// C# program to implement // the above approach using System; class GFG { static string rev( string str) { int st = 0; int ed = str.Length - 1; char [] s = str.ToCharArray(); while (st < ed) { char temp = s[st]; s[st] = s[ed]; s[ed] = temp; st++; ed--; } return new string (s); } static bool check( string a, string b, int n) { int i = 0; int j = n - 1; // iterate through the // length if we could // find a[i]==b[j] we could // increment I and decrement j while (i < n) { if (a[i] != b[j]) break ; // else we could just break // the loop as its not a // palindrome type sequence i += 1; j -= 1; // we could concatenate the // a's left part +b's right // part in a variable a and // a's right part+b's left // in the variable b string xa = a.Substring(i, j + 1 - i); string xb = b.Substring(i, j + 1 - i); // we would check for the // palindrome condition if // yes we print True else False char [] XA = xa.ToCharArray(); Array.Reverse(XA); char [] XB = xb.ToCharArray(); Array.Reverse(XB); if ( string .Compare(xa, new string (XA)) == 0 || string .Compare(xb, new string (XB)) == 0) return true ; } return false ; } // Driver code static void Main() { string a = "xbdef" ; string b = "cabex" ; if (check(a, b, a.Length) || check(b, a, a.Length)) Console.WriteLine( "True" ); else Console.WriteLine( "False" ); } } // This code is contributed by divyeshrabadiya07 |
Javascript
<script> // JavaScript program to implement // the above approach function rev(str) { var st = 0; var ed = str.length - 1; var s = str.split( "" ); while (st < ed) { var temp = s[st]; s[st] = s[ed]; s[ed] = temp; st++; ed--; } return s.join(); } function check(a, b, n) { var i = 0; var j = n - 1; // iterate through the // length if we could // find a[i]==b[j] we could // increment I and decrement j while (i < n) { if (a[i] !== b[j]) break ; // else we could just break // the loop as its not a // palindrome type sequence i += 1; j -= 1; // we could concatenate the // a's left part +b's right // part in a variable a and // a's right part+b's left // in the variable b var xa = a.substring(i, j + 1 - i); var xb = b.substring(i, j + 1 - i); // we would check for the // palindrome condition if // yes we print True else False var XA = xa.split( "" ); XA.sort().reverse(); var XB = xb.split( "" ); XB.sort().reverse(); if (xa === XA.join( "" ) || xb === XB.join( "" )) return true ; } return false ; } // Driver code var a = "xbdef" ; var b = "cabex" ; if (check(a, b, a.length) || check(b, a, a.length)) document.write( "True" ); else document.write( "False" ); </script> |
False
Time Complexity : O( | a |*| a+b |) ,where | a | is size of string a and | a+b | is size of string (a+b)
Space Complexity : O( | a+b |)
Another Approach:
The two-pointer technique is used to solve this problem. Traverse the string over its length [0, n-1]. Check if the concatenation of the substrings a [0, i-1] and b [i, n-1] or b [0, i-1] and a [i, n-1], (where i is any index) is a palindromic string or not. If it is a palindromic string, return true else return false.
Below is the implementation of this approach:
C++
// C++ code to implement the above approach #include <bits/stdc++.h> using namespace std; /*function to check if a string is palindrome or not*/ bool isPalindrome(string s){ int i=0,j=s.size()-1; while (i<=j){ if (s[i]!=s[j]){ return false ; } i++; j--; } return true ; } bool checkStrings(string &a, string &b, int n){ for ( int i=0;i<n;i++){ /*check whether the concatenation of substrings is palindrome or not*/ if ((isPalindrome(a.substr(0,i)+b.substr(i))) || (isPalindrome(b.substr(0,i)+a.substr(i))) ){ return true ; } } return false ; } int main() { string a = "xyzdef" ; string b = "rstzyx" ; int n = 6; /*if the concatenation of substring is palindrome, print true else print false*/ if (checkStrings(a,b,n)) cout<< "true" ; else cout<< "false" ; return 0; } // This code is contributed by 525tamannacse11 |
Java
import java.util.*; public class Main { /*function to check if a string is palindrome or not*/ public static boolean isPalindrome(String s) { int i = 0 , j = s.length() - 1 ; while (i <= j) { if (s.charAt(i) != s.charAt(j)) { return false ; } i++; j--; } return true ; } public static boolean checkStrings(String a, String b, int n) { for ( int i = 0 ; i < n; i++) { /*check whether the concatenation of substrings * is palindrome or not*/ if ((isPalindrome(a.substring( 0 , i) + b.substring(i))) || (isPalindrome(b.substring( 0 , i) + a.substring(i)))) { return true ; } } return false ; } public static void main(String[] args) { String a = "xyzdef" ; String b = "rstzyx" ; int n = 6 ; /*if the concatenation of substring is palindrome, * print true else print false*/ if (checkStrings(a, b, n)) { System.out.println( "true" ); } else { System.out.println( "false" ); } } } |
C#
using System; namespace PalindromeCheck { class Program { static bool IsPalindrome( string s) { int i = 0, j = s.Length - 1; while (i <= j) { if (s[i] != s[j]) { return false ; } i++; j--; } return true ; } static bool CheckStrings( ref string a, ref string b, int n) { for ( int i = 0; i < n; i++) { /*check whether the concatenation of substrings * is palindrome or not*/ if ((IsPalindrome(a.Substring(0, i) + b.Substring(i))) || (IsPalindrome(b.Substring(0, i) + a.Substring(i)))) { return true ; } } return false ; } static void Main( string [] args) { string a = "xyzdef" ; string b = "rstzyx" ; int n = 6; /*if the concatenation of substring is palindrome, * print true else print false*/ if (CheckStrings( ref a, ref b, n)) Console.WriteLine( "true" ); else Console.WriteLine( "false" ); Console.ReadKey(); } } } // This code is contributed by user_dtewbxkn77n |
Python3
# function to check if a string is palindrome or not def isPalindrome(s): i = 0 j = len (s) - 1 while i < = j: if s[i] ! = s[j]: return False i + = 1 j - = 1 return True def checkStrings(a, b, n): for i in range (n): # check whether the concatenation of substrings is palindrome or not if (isPalindrome(a[:i] + b[i:])) or (isPalindrome(b[:i] + a[i:])): return True return False a = "xyzdef" b = "rstzyx" n = 6 # if the concatenation of substring is palindrome, print true else print false if checkStrings(a, b, n): print ( "true" ) else : print ( "false" ) |
Javascript
/*function to check if a string is palindrome or not*/ function isPalindrome(s) { let i = 0, j = s.length - 1; while (i <= j) { if (s[i] != s[j]) { return false ; } i++; j--; } return true ; } function checkStrings(a, b, n) { for (let i = 0; i < n; i++) { /*check whether the concatenation of substrings is palindrome or not*/ if ((isPalindrome(a.substr(0, i) + b.substr(i))) || (isPalindrome(b.substr(0, i) + a.substr(i)))) { return true ; } } return false ; } let a = "xyzdef" ; let b = "rstzyx" ; let n = 6; /*if the concatenation of substring is palindrome, print true else print false*/ if (checkStrings(a, b, n)) console.log( "true" ); else console.log( "false" ); |
true
Time Complexity: O(n)
Space Complexity: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!