Find a palindromic string B such that given String A is a subsequence of B
Given a string . Find a string , where B is a palindrome and A is a subsequence of B.
A subsequence of a string is a string that can be derived from it by deleting some (not necessarily consecutive) characters without changing the order of the remaining characters. For example, “cotst” is a subsequence of “contest”.
A palindrome is a string that reads the same forward or backward.
Examples:
Input : A = "aba" Output : B = aba Explanation : "aba" is a subsequence of "aba" which is a palindrome. Input : A = "ab" Output : B = abba
Approach: Let reverse(s) be the reverse of a string . Now, s + reverse(s) will always have as a subsequence (as first half) and it is a palindrome.
Therefore, B = A + reverse(A).
Below is the implementation of the above approach:
C++14
// C++ program to find a palindromic string B // such that given String A is a subsequence of B #include <bits/stdc++.h> using namespace std; // Function to check if a string is palindrome bool checkPalindrome(string s) { // Reversing a string string x = s; reverse(s.begin(), s.end()); // check if reversed string is equal // to given string return s == x; } // Function to find a palindromic string B // such that given String A is a subsequence of B string findStringB(string A) { // Reversing the string A string B = A; reverse(A.begin(), A.end()); A = A + B; // If the string A is already a palindrome // return A if (checkPalindrome(B)) return B; // else return B return A; } string reverse(string input) { string temparray = input; int left, right = 0; right = temparray.length() - 1; for (left = 0; left < right; left++, right--) // Swap values of left and right swap(temparray[left], temparray[right]); return temparray; } // Driver Code int main( int argc, char const *argv[]) { string A = "ab" ; cout << findStringB(A) << endl; return 0; } // This code is contributed by // sanjeev2552 |
Java
// Java program to find a palindromic string B // such that given String A is a subsequence of B class GFG { // Function to check if a string is palindrome static boolean checkPalindrome(String s) { // Reversing a string String x = reverse(s); // check if reversed string is equal // to given string return x.equals(s); } // Function to find a palindromic string B // such that given String A is a subsequence of B static String findStringB(String A) { // Reversing the string A String B = reverse(A); B = B + A; // If the string A is already a palindrome // return A if (checkPalindrome(A)) { return A; } // else return B return B; } static String reverse(String input) { char [] temparray = input.toCharArray(); int left, right = 0 ; right = temparray.length - 1 ; for (left = 0 ; left < right; left++, right--) { // Swap values of left and right char temp = temparray[left]; temparray[left] = temparray[right]; temparray[right] = temp; } return String.valueOf(temparray); } // Driver Code public static void main(String[] args) { String A = "ab" ; System.out.println(findStringB(A)); } } // This code contributed by Rajput-Ji |
Python3
# Python program to find a palindromic string B # such that given String A is a subsequence of B # Function to check if a string is palindrome def checkPalindrome(s): # Reversing a string x = s[:: - 1 ] # check if reversed string is equal # to given string if (x = = s): return True else : return False # Function to find a palindromic string B # such that given String A is a subsequence of B def findStringB(A): # Reversing the string A B = A[:: - 1 ] B = B + A # If the string A is already a palindrome # return A if (checkPalindrome(A)): return A # else return B return B # Driver Code A = "ab" print (findStringB(A)) |
C#
// C# program to find a palindromic string B // such that given String A is a subsequence of B using System; class GFG { // Function to check if a string is palindrome static bool checkPalindrome(String s) { // Reversing a string String x = reverse(s); // check if reversed string is equal // to given string return x.Equals(s); } // Function to find a palindromic string B // such that given String A is a subsequence of B static String findStringB(String A) { // Reversing the string A String B = reverse(A); B = B + A; // If the string A is already a palindrome // return A if (checkPalindrome(A)) { return A; } // else return B return B; } static String reverse(String input) { char [] temparray = input.ToCharArray(); int left, right = 0; right = temparray.Length - 1; for (left = 0; left < right; left++, right--) { // Swap values of left and right char temp = temparray[left]; temparray[left] = temparray[right]; temparray[right] = temp; } return String.Join( "" ,temparray); } // Driver Code public static void Main(String[] args) { String A = "ab" ; Console.WriteLine(findStringB(A)); } } // This code has been contributed by 29AjayKumar |
Javascript
<script> // Javascript program to find a palindromic string B // such that given String A is a subsequence of B // Function to check if a string is palindrome function checkPalindrome(s) { // Reversing a string let x = reverse(s); // Check if reversed string is equal // to given string return x == (s); } // Function to find a palindromic string B // such that given String A is a subsequence of B function findStringB(A) { // Reversing the string A let B = reverse(A); B = B + A; // If the string A is already a palindrome // return A if (checkPalindrome(A)) { return A; } // Else return B return B; } function reverse(input) { let temparray = input.split( "" ); let left, right = 0; right = temparray.length - 1; for (left = 0; left < right; left++, right--) { // Swap values of left and right let temp = temparray[left]; temparray[left] = temparray[right]; temparray[right] = temp; } return (temparray).join( "" ); } // Driver Code let A = "ab" ; document.write(findStringB(A)); // This code is contributed by rag2127 </script> |
Output
baab
Time Complexity: O(n), where n is the length of the given string.
Auxiliary Space: O(n), where n is the length of the given string.