Lapindrome problem

can i know where i am wrong i even seperated when length is odd
#include <bits/stdc++.h>
using namespace std;
int check(string s){

  int l,c=0,mid;
  l=s.length();
      bool vis[l-1];
      mid=l/2;

     if(l%2!=0){
       mid=(l/2)+1;
        vis[mid-1]=true;
      for(int i=0;i<mid-1;i++){
        for(int j=mid;j<l;j++){
         if(s[i]==s[j]&&vis[j]!=true){
             vis[j]=true;
             vis[i]=true;
             c=1;
             break;
         }
         else
         c=0;
    }
    if(c==0)
    break;
    }
    }
    else{
		mid=l/2;
	for(int i=0;i<mid;i++){
        for(int j=mid;j<l;j++){
         if(s[i]==s[j]&&vis[j]!=true){
             vis[j]=true;
             vis[i]=true;
             c=1;
             break;
         }
         else
         c=0;
    }
    if(c==0)
    break;	
	}
    }

return c;
}
int main() {
int t,c;
string s;
cin>>t;
while(t–){
cin>>s;
c=check(s);
if(c==0)
cout<<“NO”<<endl;
else if(c==1)
cout<<“YES”<<endl;

}
return 0;
}

  1. Post the link to the problem.
  2. Format the code or post link for better readability.

I think you have misinterpreted the problem. It does not say that the order of the letters should be same instead only the count of the letters needs to be equal.

Eg:

Input:
aabccacbcaaa

Output :
YES

2 Likes

format your code using ``` (three backticks) before and after the code.


#include < iostream>
#include < vector>
#include < string>
using namespace std;
int main() {
	// your code goes here
	vector<string>name;
	int t, a[26], b[26];
	cin >> t;
	for(int i = 0; i < t; i++){         //storing names in a vector
	    string str;
	    cin >> str;
	    name.push_back(str);
	}
	for(int i = 0; i <= 26; i++){        // initialising arrays
	    a[i] = 0;
	    b[i] = 0;
	}
	for(int i = 0; i < t; i ++){
	    string n = name[i];
	    string sub1, sub2;
	    if(t % 2 == 0){
	        sub1 = n.substr(0, n.length()/2);                   //division of string if length is even
	        sub2 = n.substr(n.length()/2 + 1, n.length() - 1);
	    }
	    else
	    {
	        sub1 = n.substr(0, n.length()/2);
	        sub2 = n.substr((n.length()+1)/2, n.length() - 1);  //division of string if length is odd
	    }
	    for(int i = 0; i < sub1.length(); i++){
	        if(a[sub1[i]-97] == 0){               //placing characters accorrding to ASCII values in sub1
	            a[sub1[i]-97] =  1;
	        }else{
	            a[sub1[i]-97] ++;
	        }
	    }
	    for(int i = 0; i < sub2.length(); i++){
	        if(b[sub2[i]-97] != 0){               //placing characters accorrding to ASCII values in sub2
	            b[sub2[i]-97] =  1;
	        }else{
	            b[sub2[i]-97] ++;
	        }
    	}
    	bool ans = true;
    	for(int i = 0; i < 26; i++){
    	    if(a[i] != b[i]){
    	        ans = false;
    	        break;
    	    }
    	}
    	
        if(ans){
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
	}
    	
	return 0;
}

This is my solution… if i try to give input one by one, i am getting correct answer but as soon as i give multiple inputs together, all answers turn to no. Can you help ? I am trying to debug since last one and a half hour.

I think the place where you are initialising A and B with zeroes should be common for every test case.

It’s initialised only once and after each test case which will be processed the count of it’s characters will remain in A and B for the next one too.

You can confirm it by running a small code like below in your main program that you r running for each test case.

for (int i =0; i< 26; i++) {
		cout << "A" <<i<< "=" <<a[i] << "\n";
		cout << "B" <<i<< "=" <<b[i] << "\n";
	}

Tip for debugging, its always easier to debug your variables before and after each test cases to see the changes occuring in them and to see if they were properly initialised.

1 Like

I corrected the code, there is one more problem now
try the test case
2
gaga
rotor
you will receive the output
NO
YES
I tried to see if the arrays a[] and b[] were correctly filled and then saw that my arrays were filling with garbage values infinitely… My array size is still 26, yet so many entries.
why is this happening ?

Can you provide your corrected code or a link. I will run it on my system for possible errors.

Edit :

Nevermind, I have found a few potential errors in your code .

  1. The parent for loop with i from 0 -> t has a nested for with same variable name i for counting letters in substrings, this may lead to undefined behaviour.

  2. When you are dividing the string into sub1 and sub2, you are considering t % 2 which should be (length of string) % 2.

  3. Garbage values can arise due to undefined behaviour of index out of bounds possibly because of above 2 reasons.

1 Like

Wait i fixed it… now just one small help, the code is not working for gaga while taking multiple inputs, it is not putting the ‘g’ from second substring into the array. I tried changing the order of inputs also.

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int main() {
	// your code goes here
	vector<string>name;
	int t, a[26], b[26];
	cin >> t;
	for(int i = 0; i < t; i++){         //storing names in a vector
	    string str;
	    cin >> str;
	    name.push_back(str);
	}
	
	for(int i = 0; i < t; i ++){
	    for(int i = 0; i < 26; i++){        // initialising arrays
	    a[i] = 0;
	    b[i] = 0;
	    }
	    string n = name[i];
	    string sub1, sub2;
	    if(t % 2 == 0){
	        sub1 = n.substr(0, n.length()/2);                   //division of string if length is even
	        sub2 = n.substr(n.length()/2 + 1, n.length() - 1);
	    }
	    else
	    {
	        sub1 = n.substr(0, n.length()/2);
	        sub2 = n.substr((n.length()+1)/2, n.length() - 1);  //division of string if length is odd
	    }
	    for(int i = 0; i < sub1.length(); i++){
	        if(a[sub1[i]-97] == 0){               //placing characters accorrding to ASCII values in sub1
	            a[sub1[i]-97] =  1;
	        }else{
	            a[sub1[i]-97] ++;
	        }
	    }
	    for(int i = 0; i < sub2.length(); i++){
	        if(b[sub2[i]-97] == 0){               //placing characters accorrding to ASCII values in sub2
	            b[sub2[i]-97] =  1;
	        }else{
	            b[sub2[i]-97] ++;
	        }
    	}
    	
    	for(int i = 0; i < 26; i++){
    	    cout << a[i] << " " << b[i] << endl;
    	}
    	cout << "next" << endl;
    	/*bool ans = true;
    	for(int i = 0; i < 26; i++){
    	    if(a[i] != b[i]){
    	        ans = false;
    	        break;
    	    }
    	}
    	
        if(ans){
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }*/
	}
    	
	return 0;
}

I see that you have not changed (t % 2 == 0). It should be (lengthOfN % 2 == 0).

Next, the substring method in C++ works as following:
substr(i, j) -> string starting from i and having length j. i.e. string[i]+string[i+1]+…string[i+j-1].

reference

That might be the problem ig.
I use Python for almost all string related problems, so it’s better you read from the reference and so will I. :slight_smile:

Consider Case 1:
rotor
r o t o r
0 1 2 3 4
len = 5, the two desired substrings are ro and or.
size of both the desired substring is sz = floor(len / 2)

We get ro by substr(0, 2) and or by substr(3, 2), which is equivalent to
substr(0, sz) and substr(sz+1, sz).

Case 2:
gaga
g a g a
0 1 2 3

len = 4, the two desired substrings are ga and ga.
size of both the desired substring is sz = floor(len / 2)

We get ga by substr(0, 2) and the other ga by substr(2, 2), which is equivalent to
substr(0, sz) and substr(sz, sz).

1 Like

Solved it… Thank you :slight_smile:

2 Likes

check the format if its k
no i did understand my code is working in my compiler but when i am running in the codechef getting no for each you can check

getting the answer Yes can u check once more

Well it’s giving NO on every case in my env as well.

I will try to debug it & in the meanwhile if you explain your logic it will be more helpful.

Also, I suggest you to try and think of a different approach for the problem. Your current approach may time out in the given constraints as it is \mathcal O (n^2).

In the other approaches you can think of the strings as just some collection of letters and the only thing you are concerned about is the count of each individual character in the two halves.

hmm well my idea was k idk why it was not working as u said it was O(n^2)
so i just made it simple thanks

#include<bits/stdc++.h>
using namespace std;
void solve(){
	string s,s1,s2;
	int h;
	bool test=true;
	cin>>s;
	int l=s.length();
	if(l&1){
		h=l/2;
	    s1=s.substr(0,h);
	    s2=s.substr((h+1),l);
		}
	else{
		h=l/2;
		s1=s.substr(0,h);
	    s2=s.substr(h,l);
		}
     for(char c='a';c<='z';c++){
		 if(count(s1.begin(),s1.end(),c)!=count(s2.begin(),s2.end(),c)){
			 test=false;
			 break;
			 }
		 }
     if(test==true)
     cout<<"YES"<<endl;
     else
     cout<<"NO"<<endl;
	}
int main(){
	int t;
	cin>>t;
	while(t--)
	solve();
	}
1 Like