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 notbool 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 palindromevoid 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 Codeint 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 approachimport 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 notdef 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 # palindromedef 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 Codeif __name__ == "__main__": A = "bdea" B = "abbb" N = 4 formPalindrome(A, B, N)# This code is contributed by Chitranayal |
C#
// C# program for the // above approachusing System;using System.Text;class GFG{// Function to check if a string// is palindrome or notstatic 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 palindromestatic 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 Codepublic 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 notfunction 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 palindromefunction 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> |
Output
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 codeint 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 approachimport 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 Codepublic 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 approachdef 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 Truea = "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 approachusing 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> |
Output
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 notdef isPalindrome(s): i = 0 j = len(s) - 1 while i <= j: if s[i] != s[j]: return False i += 1 j -= 1 return Truedef 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 Falsea = "xyzdef"b = "rstzyx"n = 6# if the concatenation of substring is palindrome, print true else print falseif 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"); |
Output
true
Time Complexity: O(n)
Space Complexity: O(1)
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!
