Check if there exist a string Y such that (X+Y) and (Y+X) are palindromes
Given a string X of length N and an integer K, the task is to determine if there exists a string (say Y) of length K such that its concatenation on either side of X makes the resultant string palindrome i.e. X+Y and Y+X both are palindromes.
Examples:
Input: N = 6, K = 2, X = “abbaab”
Output: Yes
Explanation: Let string Y = “ba”. Then,
X + Y = “abbaabba” (which is a palindrome)
Y + X = “baabbaab” (which is also a palindrome).Input: N = 12, K = 400378271514996652, X = “njvhhvjnnjvh”
Output: Yes
Approach: To solve the problem follow the below observations:
Observations:
Case 1: K < 2*N
Let rev(X) represent the reverse of string X. If K<2*N, the leftmost min(N, K) characters of Y should be equal to rev(X), and so the rightmost min(N, K) characters. So, we know that there exist a string that can satisfy the conditions. We just have to find it and check if it satisfies the conditions.
Case 2: K >= 2*N
K can be replaced with K%(2*N) so that Case-2 becomes equivalent to Case-1, however the problem won’t be affected.
Proof:
There is string Y (|Y| = K) such that X+Y, Y+X are palindromes. Let string Y (|Y| = K – 2N) be such that X + rev(X) + Y + rev(X),
rev(X) + Y + rev(X) + X are palindromes
- rev(X)+Y, Y+rev(X) are palindromes
- rev(rev(X)+Y), rev(Y+rev(X)) are palindromes
- rev(Y)+X, X+rev(Y) are palindromes
- Y+X, X+Y are palindromes.
Based on the above observations, the following steps can be used to solve the problem :
- Reverse the given string X
- Replace K with K%(2N)
- Initialize a string (say temp) of size K.
- Iterate through the initial min(N, K) characters of X and make the ith character of temp equal to the ith character from the end of the string X.
- Again, iterate through min(N, K). If an ith character from the end of temp is not filled yet, make it equal to ith character of X. Else, if it is filled and not equal to X[i], return “No”.
- At the end of the iteration, check if both X+temp and temp+X are palindromes. If so, return “Yes”, else return “No”.
Following is the code based on the above approach:
C++
// C++ code for the above approach #include <bits/stdc++.h> using namespace std; #define int long long // Function to check if given string is // a palindrome or not bool isPalindrome(string S) { for (int i = 0; i < S.size(); i++) { if (S[i] != S.end()[-1 - i]) return false; } return true; } // Function to Check if there exist a // string Y such that (X+Y) and (Y+X) // are palindromes void isPossible(string X, int N, int K) { // Reverse string X reverse(X.begin(), X.end()); // Updating K K %= (2 * N); // Declaring and Initializing a // string temp string temp(K, '.'); // Iterating from i=0 to min(K-1, N-1) for (int i = 0; i < K && i < N; i++) { // Making ith character of temp // equal to ith character from // the end of X temp[i] = X[N - 1 - i]; } // Iterating from i=0 to min(K-1, N-1) for (int i = 0; i < K && i < N; i++) { // If ith character from end of // temp is not filled yet, make it // equal to ith character of X if (temp[K - 1 - i] == '.') temp[K - 1 - i] = X[i]; // Else if it is filled and not // equal to X[i], print "No" // and return else { if (X[i] != temp[K - 1 - i]) { cout << "No" << endl; return; } } } // If both (X+temp) and (temp+X) are // palindrome, print yes if (isPalindrome(X + temp) && isPalindrome(temp + X)) cout << "Yes" << endl; // Else print No else cout << "No" << endl; } // Driver code int32_t main() { int N = 6, K = 2; string S = "abbaab"; // Function Call isPossible(S, N, K); return 0; }
Java
import java.util.*; class Main { // Function to check if given string is // a palindrome or not public static boolean isPalindrome(String S) { for (int i = 0; i < S.length(); i++) { if (S.charAt(i) != S.charAt(S.length() - 1 - i)) { return false; } } return true; } // Function to Check if there exist a // string Y such that (X+Y) and (Y+X) // are palindromes public static void isPossible(String X, int N, int K) { // Reverse string X StringBuilder reversed = new StringBuilder(X); reversed = reversed.reverse(); X = reversed.toString(); // Updating K K %= (2 * N); // Declaring and Initializing a // string temp char[] temp = new char[K]; Arrays.fill(temp, '.'); // Iterating from i=0 to min(K-1, N-1) for (int i = 0; i < K && i < N; i++) { // Making ith character of temp // equal to ith character from // the end of X temp[i] = X.charAt(N - 1 - i); } // Iterating from i=0 to min(K-1, N-1) for (int i = 0; i < K && i < N; i++) { // If ith character from end of // temp is not filled yet, make it // equal to ith character of X if (temp[K - 1 - i] == '.') { temp[K - 1 - i] = X.charAt(i); } // Else if it is filled and not // equal to X[i], print "No" // and return else { if (X.charAt(i) != temp[K - 1 - i]) { System.out.println("No"); return; } } } // If both (X+temp) and (temp+X) are // palindrome, print yes if (isPalindrome(X + new String(temp)) && isPalindrome(new String(temp) + X)) { System.out.println("Yes"); } // Else print No else { System.out.println("No"); } } // Driver code public static void main(String[] args) { int N = 6, K = 2; String S = "abbaab"; // Function Call isPossible(S, N, K); } }
Python3
# Python code for the above approach # Function to check if given string is # a palindrome or not def isPalindrome(S): for i in range(len(S)): if S[i] != S[-1 - i]: return False return True # Function to check if there exist a # string Y such that (X+Y) and (Y+X) # are palindromes def isPossible(X, N, K): # Reverse string X X = X[::-1] # Updating K K %= (2 * N) # Declaring and Initializing a # string temp temp = K * '.' # Iterating from i=0 to min(K-1, N-1) for i in range(min(K, N)): # Making ith character of temp # equal to ith character from # the end of X temp = temp[:i] + X[N - 1 - i] + temp[i+1:] # Iterating from i=0 to min(K-1, N-1) for i in range(min(K, N)): # If ith character from end of # temp is not filled yet, make it # equal to ith character of X if temp[K - 1 - i] == '.': temp = temp[:K - 1 - i] + X[i] + temp[K - i:] # Else if it is filled and not # equal to X[i], print "No" # and return else: if X[i] != temp[K - 1 - i]: print("No") return # If both (X+temp) and (temp+X) are # palindrome, print "Yes" if isPalindrome(X + temp) and isPalindrome(temp + X): print("Yes") # Else print "No" else: print("No") # Driver code N, K = 6, 2 S = "abbaab" # Function Call isPossible(S, N, K) # This code is contributed by prasad264
C#
using System; using System.Text; public class GFG{ // Function to check if given string is // a palindrome or not public static bool isPalindrome(string S) { for (int i = 0; i < S.Length; i++) { if (S[i] != S[S.Length - 1 - i]) { return false; } } return true; } // Function to Check if there exist a // string Y such that (X+Y) and (Y+X) // are palindromes public static void isPossible(string X, int N, int K) { // Reverse string X StringBuilder sb = new StringBuilder(); for (int i = X.Length - 1; i >=0 ; i--) { sb.Append(X[i]); } X = sb.ToString(); // Updating K K %= (2 * N); // Declaring and Initializing a // string temp char[] temp = new char[K]; Array.Fill(temp, '.'); // Iterating from i=0 to min(K-1, N-1) for (int i = 0; i < K && i < N; i++) { // Making ith character of temp // equal to ith character from // the end of X temp[i] = X[N - 1 - i]; } // Iterating from i=0 to min(K-1, N-1) for (int i = 0; i < K && i < N; i++) { // If ith character from end of // temp is not filled yet, make it // equal to ith character of X if (temp[K - 1 - i] == '.') { temp[K - 1 - i] = X[i]; } // Else if it is filled and not // equal to X[i], print "No" // and return else { if (X[i] != temp[K - 1 - i]) { Console.WriteLine("No"); return; } } } // If both (X+temp) and (temp+X) are // palindrome, print yes if (isPalindrome(X + new string(temp)) && isPalindrome(new string(temp) + X)) { Console.WriteLine("Yes"); } // Else print No else { Console.WriteLine("No"); } } // Driver code static public void Main (){ int N = 6, K = 2; String S = "abbaab"; // Function Call isPossible(S, N, K); } }
Javascript
// JavaScript code for the above approach function isPalindrome(S) { for (let i = 0; i < S.length; i++) { if (S[i] !== S[S.length - 1 - i]) { return false; } } return true; } function isPossible(X, N, K) { // Reverse string X X = X.split("").reverse().join(""); // Updating K K %= 2 * N; // Declaring and Initializing a // string temp let temp = ".".repeat(K); // Iterating from i=0 to min(K-1, N-1) for (let i = 0; i < Math.min(K, N); i++) { // Making ith character of temp // equal to ith character from // the end of X temp = temp.substr(0, i) + X[N - 1 - i] + temp.substr(i + 1); } // Iterating from i=0 to min(K-1, N-1) for (let i = 0; i < Math.min(K, N); i++) { // If ith character from end of // temp is not filled yet, make it // equal to ith character of X if (temp[K - 1 - i] === ".") { temp = temp.substr(0, K - 1 - i) + X[i] + temp.substr(K - i); } // Else if it is filled and not // equal to X[i], print "No" // and return else if (X[i] !== temp[K - 1 - i]) { console.log("No"); return; } } // If both (X+temp) and (temp+X) are // palindrome, print yes if (isPalindrome(X + temp) && isPalindrome(temp + X)) { console.log("Yes"); } // Else print No else { console.log("No"); } } // Driver code let N = 6, K = 2; let S = "abbaab"; // Function Call isPossible(S, N, K);
Yes
Time Complexity : O(min(N, K))
Auxiliary Space : O(K)