CONCATPAL - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: jeevanjyot
Testers: iceknight1093, rivalq
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

You have two strings A and B, which you can rearrange as you wish to form A' and B'.
Is it possible to make A'+B' a palindrome?

EXPLANATION:

Suppose N \leq M, i.e, A is the shorter string.

Now, suppose we’re able to obtain A' and B' such that A'+B' is a palindrome.
Since N \leq M, this means that:

  • The last N characters of B' must exactly form A'.
  • The remaining M - N characters of B' must form a palindrome among themselves.

Notice that this isn’t too hard to check:

  • Let \text{freq}_A[c] denote the number of occurrences of c in A. Similarly define \text{freq}_B[c].
  • The first condition then simply says that \text{freq}_A[c] \leq \text{freq}_B[c] for every character c from 'a' to 'z'.
    • This can be checked quite easily by just building both frequency tables.
  • The second condition requires us to check whether all the remaining characters can form a palindrome via rearrangement.
    • This is a rather classical task, and has a simple solution: a list of characters can be rearranged to form a palindrome if and only if at most one of them occurs an odd number of times.
    • Notice that this is also easy to check with the frequency tables we have: the number of c such that (\text{freq}_B[c] - \text{freq}_A[c]) is odd should be \leq 1.

The answer is affirmative if and only if both conditions above are satisfied.

If N \gt M just swap A and B and apply the above algorithm anyway.

TIME COMPLEXITY

\mathcal{O}(N) per test case.

CODE:

Setter's code (C++)
#ifdef WTSH
    #include <wtsh.h>
#else
    #include <bits/stdc++.h>
    using namespace std;
    #define dbg(...)
#endif

#define int long long
#define endl "\n"
#define sz(w) (int)(w.size())
using pii = pair<int, int>;

const long long INF = 1e18;

const int N = 1e6 + 5; 

// -------------------- Input Checker Start --------------------

long long readInt(long long l, long long r, char endd)
{
    long long x = 0;
    int cnt = 0, fi = -1;
    bool is_neg = false;
    while(true)
    {
        char g = getchar();
        if(g == '-')
        {
            assert(fi == -1);
            is_neg = true;
            continue;
        }
        if('0' <= g && g <= '9')
        {
            x *= 10;
            x += g - '0';
            if(cnt == 0)
                fi = g - '0';
            cnt++;
            assert(fi != 0 || cnt == 1);
            assert(fi != 0 || is_neg == false);
            assert(!(cnt > 19 || (cnt == 19 && fi > 1)));
        }
        else if(g == endd)
        {
            if(is_neg)
                x = -x;
            if(!(l <= x && x <= r))
            {
                cerr << "L: " << l << ", R: " << r << ", Value Found: " << x << '\n';
                assert(false);
            }
            return x;
        }
        else
        {
            assert(false);
        }
    }
}

string readString(int l, int r, char endd)
{
    string ret = "";
    int cnt = 0;
    while(true)
    {
        char g = getchar();
        assert(g != -1);
        if(g == endd)
            break;
        cnt++;
        ret += g;
    }
    assert(l <= cnt && cnt <= r);
    return ret;
}

long long readIntSp(long long l, long long r) { return readInt(l, r, ' '); }
long long readIntLn(long long l, long long r) { return readInt(l, r, '\n'); }
string readStringSp(int l, int r) { return readString(l, r, ' '); }
string readStringLn(int l, int r) { return readString(l, r, '\n'); }
void readEOF() { assert(getchar() == EOF); }

vector<int> readVectorInt(int n, long long l, long long r)
{
    vector<int> a(n);
    for(int i = 0; i < n - 1; i++)
        a[i] = readIntSp(l, r);
    a[n - 1] = readIntLn(l, r);
    return a;
}

// -------------------- Input Checker End --------------------


int sumN = 0;
void solve()
{
    int n = readIntSp(1, 2e5);
    int m = readIntLn(1, 2e5);
    sumN += n + m;
    string a = readStringLn(n, n);
    string b = readStringLn(m, m);
    for(auto &x: a) assert(x >= 'a' and x <= 'z');
    for(auto &x: b) assert(x >= 'a' and x <= 'z');
    if(n > m)
        swap(a, b), swap(n, m);
    array<int, 26> a_cnt{}, b_cnt{};
    for(auto &x: a)
        a_cnt[x - 'a']++;
    for(auto &x: b)
        b_cnt[x - 'a']++;
    bool ok = true;
    int odd = 0;
    for(int i = 0; i < 26; i++)
    {
        if(b_cnt[i] < a_cnt[i])
            ok = false;
        odd += (b_cnt[i] - a_cnt[i]) % 2;
    }
    if(odd <= 1 and ok)
        cout << "YES\n";
    else
        cout << "NO\n";
}

int32_t main()
{
    ios::sync_with_stdio(0); 
    cin.tie(0);
    int T = readIntLn(1, 2e5);
    for(int tc = 1; tc <= T; tc++)
    {
        // cout << "Case #" << tc << ": ";
        solve();
    }
    assert(sumN <= 2e5);
    readEOF();
    return 0;
}
Editorialist's code (Python)
for _ in range(int(input())):
	n, m = map(int, input().split())
	freq = {}
	for c in input():
		add = (n >= m) - (n < m)
		if c in freq: freq[c] += add 
		else: freq[c] = add
	for c in input():
		add = (m > n) - (m <= n)
		if c in freq: freq[c] += add 
		else: freq[c] = add
	odd = 0
	for y in freq.values():
		odd += y%2
	print('YES' if odd <= 1 and min(freq.values()) >= 0 else 'NO')

Can you please explain me why this code gives wrong answer on task #1

#include <bits/stdc++.h>
using namespace std;

int main() {
	// your code goes here
	int t ;
	cin >> t ;
	while(t--){
	        int count = 0 ;
	    int n , m ;
	    cin >> n >> m ;
	    string s1 ;
	    string s2 ;
	    cin>>s1>>s2;
	    string str = s1 + s2 ;
	    unordered_map<char, int> M;
     for (int i = 0; i<n+m; i++){
            if (M.find(str[i]) == M.end()){
            M.insert(make_pair(str[i], 1));
        }
        else{
            M[str[i]]++;
        }
    }
     for (auto& it : M) {
       if(((it.second)%2)==1){
           count ++ ;
       }
    }
    if(count > 1){
        cout << "NO" ;
    }
    else cout << "YES" ;
    cout << endl ;
	}
	return 0;
}

1 Like

THIS CODE IS NOT WORKING FOR 1 TESTCASE AFTER SUBMISSION CAN ANYONE HELP

 #include<bits/stdc++.h>
using namespace std;

int main(){
   long long  t;
   cin>>t;
   while(t--){
    long long  n1,n2;
    cin>>n1>>n2;
    string s1,s2;
    cin>>s1>>s2;
    string fstring;
    fstring = s1+s2;
    if(fstring.size()==1||n2==0){
        cout<<"YES"<<endl;
    }
    int arr[26]= { 0 };
    for(int i=0;i<fstring.size();i++){
        arr[fstring[i]-'a']++;

    }
    long long  ans=0;
    for(int i=0;i<26;i++){
        if(arr[i]%2!=0){
         ans++;
        }

    }
    if(ans<=1){
        cout<<"YES"<<endl;
    }
    else{
        cout<<"NO"<<endl;
    }


    
}
}
2 Likes

[Editorial Solution]
(CONCATPAL Problem - CodeChef)

*** This is a rather classical task, and has a simple solution: a list of characters can be rearranged to form a palindrome if and only if at most one of them occurs an odd number of times. ****

//// if and only if at most one of them occurs an odd number of times //////

what if M-N is even ?? in that case if any character occurs odd number of times or even 1 time only, than how can that part be palindromic??

If the length is even and one character appears an odd number of times, then some other character will also appear an odd number of times. so there’ll be at least 2 characters occurring an odd number of times.

So yes, if M-N is even, every character must occur an even number of times for it to be able to form a palindrome.

The \leq 1 statement I made is just a nice way of combining the even and odd cases together.

I don’t know if I am missing something but I am not able to figure out the reason for error in my code.
Link to submission Click
In my code I have compared string a,b ( a is longer string) whatever character of a are not present in string in string b, I add them to new string str. Then I am checking if the string str can made as palindrome ( using odd_count <= 1 to be a palindrome). Can someone pls check once.

Could someone help me understand what is wrong with my code ? I always get WA on the second test, but pass all the others.

Here is my logic:

  • If the length of A'+B' is even, the only way to form a palindrome is when each character occurs an even number of time
  • If the length of A'+B' is odd, the only way to form a palindrome is also when each character occurs an even number of time, but with a middle part in it. The middle part is discoverable because it has an odd length
public class Main {	
	public static void main(String[] args) {
		try(Scanner scn = new Scanner(System.in)) {
			int cases = scn.nextInt();
			while(cases-- > 0) {
				int l1 = scn.nextInt(); // Length of string A
				int l2 = scn.nextInt(); // Length of string B
				String s1 = scn.next(); // String A
				String s2 = scn.next(); // String B
				 
				int total_length = l1 + l2; // Length of A+B
				String concat = s1 + s2; // A + B
				int[] letters = new int[26]; // Frequency array
				
				String answ = "YES"; // Default answer
				int diff = 0;
				
				// Building the frequencies
				for(int i = 0; i < total_length; ++i) {
					++letters[concat.charAt(i) - 'a'];
				}
				
				// Counting characters that appear an odd number of time
				for(int i = 0; i < 26; ++i) {
					 if(letters[i] != 0 && letters[i] % 2 != 0) {
						++diff;
					}
				}
				
				// If several caracters appear an odd number of time, then no
				if(diff > 1)
					answ = "NO";
				
				System.out.println(answ);
			}
		}
	}
}

Why this gives WA only in Task# 1?

void solve()
{
    int a, b;
    cin >> a >> b;
    
    string s1, s2;
    cin >> s1 >> s2;
    
    int arr[26] = {0};
    
    for (int i = 0; i < a; i++)
    {
        arr[s1[i] - 'a']++;
    }
    
    for (int i = 0; i < b; i++)
    {
        arr[s2[i] - 'a']++;
    }
    
    int sum = 0;
    
    for (int i = 0; i < 26; i++)
    {
        sum+=arr[i];
        if(arr[i]%2!=0)
            sum--;
    }
    
    if(sum/2 == (a+b)/2) cout<<"yes"<<endl;
    else cout<<"no"<<endl;
}

this is the test case where my solution fail according to codechef’s debugger.

1
1 2
a
bb

my output is ‘yes’ but expected output is ‘no’.
i donot get it, isn’t ‘bab’ a palindrome?

you can only rearrange each string individually and then concatenate it
so if you rearrange ‘A’ it will remain ‘a’ all the time and if you rearrange B it will also remain ‘bb’ all the time so if you add them now you can only get ‘abb’ which is not a palindrome

You have to rearrange A and B separately into A’ and B’ so that A’+B’ forms a palindrome. You are rearranging A+B directly that’s why you are getting wrong answer.
Consider a case where A=“aabb”, B=“ccdd”.
Here, your code will say that A’+B’ can be a palindrome, which is not true. No matter how you rearrange A and B and concatenate them later on, it won’t give you a palindrome.
I hope I cleared your doubt :slight_smile:

You have to rearrange A and B separately into A’ and B’ so that A’+B’ forms a palindrome. You are rearranging A+B directly that’s why you are getting wrong answer.
Consider a case where A=“aabb”, B=“ccdd”.
Here, your code will say that A’+B’ can be a palindrome, which is not true. No matter how you rearrange A and B and concatenate them later on, it won’t give you a palindrome.
I hope I cleared your doubt :slight_smile:
Try to see the tutorial for more clarity.

1 Like

Ooooh I understand now. Thank you very much, I will try it again :smile:

Guys can someone help me to find at what test cases this gives wrong output ,
I renamed all of my variables to make it readable , I will appreciate the help
for i in range(int(input())):

len1,len2=input().split()

str1=input()

str2= input()

freq={}

if(len2>len1):

    str1,str2=str2,str1

for i in str1:

    if(i in freq):

        freq[i]+=1

    else:

        freq[i]=1

for i in str2 :

    if(i in freq ):

        freq[i]-=1

    else:

        freq[i]=-1

odd=0

ans=1

for i in freq:

    if(freq[i]<0):

        ans=0

        break

    if(freq[i]%2==1):

        odd+=1

if(odd<=1 and ans==1):

    print("Yes")

else:

    print("No")

why does this give wA??
Solution: 89975544 | CodeChef

Your code gives wrong output for this test case:
Consider “aa” and “bb”. There is no way to rearrange those two strings individually and get a palindrome by combining them. So the output should be “NO” but your program says “YES”.

1 Like

My code fails on a test case and I am not able to figure out where… Can someone please help me find it?
Here is my code: CodeChef: Practical coding for everyone

yeah got it yesterday after reading the question carefully, i was see the 2 string as a whole 1 string :,) and checking it whether it was yes or no

making it way tooo complicated,
here check this – Solution: 89985080 | CodeChef

i have written the explanation in the comments.

1 Like

I understood your approach but I was hoping to know where my code fails since it seems correct to me… Nevertheless, thank you very much.

1 Like