https://write.neveropen.co.uk/internshipGiven three strings S1, S2, and S3 of lengths L, M, and N respectively, the task is to check if it is possible to choose some non-empty substrings from S1, S2, and S3 such that their concatenation is a palindrome. If found to be true, print “YES”. Otherwise, print “NO”.
Examples:
Input: S1 = “adcb”, S2 = “bcdb”, S3 = “ace”
Output: YES
Explanation:
One of the possible ways is as follows:
Select substring “ad” from the string S1, “d” from the string S2, and “a” from the string S3. Therefore, the resultant string is S = “adda”, which is a palindrome. Therefore, the output should be “YES”.Input: S1 = “a”, S2 = “bc”, S3 = “c”
Output: NO
Approach: The idea is to observe that it is always possible to find such a, b, and c such that a+b+c becomes palindrome if S1 and S3 have at least one common character. Follow the below steps to solve the problem:
- Initialize two variables, say maskA and maskC, for masking the characters in the strings S1 and S3 respectively.
- Iterate over the characters of the string S1 and set (i-‘a’)th bit in maskA, indicating that the respective character is present in string S1.
- Iterate over characters of the string S3 and set (i-‘a’)th bit in maskC, indicating that the respective character is present in string S3.
- If the Bitwise AND of maskA and maskC is greater than zero, then 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 substrings from// three given strings can be concatenated// to form a palindromestring make_palindrome( string S1, string S2, string S3){ // Mask for S1 and S2 int maskA = 0, maskC = 0; // Set (i-'a')th bit in maskA for (char i : S1) maskA |= (1 << (i - 'a')); // Set (i-'a')th bit in maskC for (char i : S3) maskC |= (1 << (i - 'a')); // If the bitwise AND is > 0 if ((maskA & maskC) > 0) return "YES"; return "NO";}// Driver Codeint main(){ string S1 = "adcb", S2 = "bcdb", S3 = "abe"; cout << make_palindrome(S1, S2, S3);} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to check if subStrings from// three given Strings can be concatenated// to form a palindromestatic String make_palindrome( String S1, String S2, String S3){ // Mask for S1 and S2 int maskA = 0, maskC = 0; // Set (i-'a')th bit in maskA for (char i : S1.toCharArray()) maskA |= (1 << (i - 'a')); // Set (i-'a')th bit in maskC for (char i : S3.toCharArray()) maskC |= (1 << (i - 'a')); // If the bitwise AND is > 0 if ((maskA & maskC) > 0) return "YES"; return "NO";}// Driver Codepublic static void main(String[] args){ String S1 = "adcb", S2 = "bcdb", S3 = "abe"; System.out.print(make_palindrome(S1, S2, S3));}}// This code is contributed by shikhasingrajput |
Python3
# Python3 program for the above approach# Function to check if substrings from# three given strings can be concatenated# to form a palindromedef make_palindrome(S1, S2, S3): # Mask for S1 and S2 maskA, maskC = 0, 0 # Set (i-'a')th bit in maskA for i in S1: maskA |= (1 << (ord(i) - ord('a'))) # Set (i-'a')th bit in maskC for i in S3: maskC |= (1 << (ord(i) - ord('a'))) # If the bitwise AND is > 0 if ((maskA & maskC) > 0): return "YES" return "NO"# Driver Codeif __name__ == '__main__': S1,S2,S3 = "adcb", "bcdb", "abe" print (make_palindrome(S1, S2, S3)) # This code is contributed by mohit kumar 29. |
C#
// C# program for the above approachusing System;public class GFG{// Function to check if subStrings from// three given Strings can be concatenated// to form a palindromestatic String make_palindrome( String S1, String S2, String S3){ // Mask for S1 and S2 int maskA = 0, maskC = 0; // Set (i-'a')th bit in maskA foreach (char i in S1.ToCharArray()) maskA |= (1 << (i - 'a')); // Set (i-'a')th bit in maskC foreach (char i in S3.ToCharArray()) maskC |= (1 << (i - 'a')); // If the bitwise AND is > 0 if ((maskA & maskC) > 0) return "YES"; return "NO";}// Driver Codepublic static void Main(String[] args){ String S1 = "adcb", S2 = "bcdb", S3 = "abe"; Console.Write(make_palindrome(S1, S2, S3));}}// This code is contributed by Rajput-Ji |
Javascript
<script>// Javascript program for the above approach// Function to check if subStrings from// three given Strings can be concatenated// to form a palindromefunction make_palindrome(S1,S2,S3){ // Mask for S1 and S2 let maskA = 0, maskC = 0; // Set (i-'a')th bit in maskA for (let i=0;i< S1.length;i++) maskA |= (1 << (S1[i].charCodeAt(0) - 'a'.charCodeAt(0))); // Set (i-'a')th bit in maskC for (let i=0;i< S3.length;i++) maskC |= (1 << (S3[i].charCodeAt(0) - 'a'.charCodeAt(0))); // If the bitwise AND is > 0 if ((maskA & maskC) > 0) return "YES"; return "NO";}// Driver Codelet S1 = "adcb", S2 = "bcdb", S3 = "abe";document.write(make_palindrome(S1, S2, S3));// This code is contributed by unknown2108</script> |
Output:
YES
Time Complexity: O(L + N)
Auxiliary Space: O(L + M + N)
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!
