Construct String

This was a problem of the Starters 83 Division Contest of CodeChef and was I think the 4th or the 5th problem from the starting and was kinda medium level problem. I had implemented this problem in Python3 at first but this current implementation is in C++17. The overall test in this problem was according to me how we detect the pattern that is being made in the Process, and the usage of String traversal alongwith while loop, bcz this would have been done with a for loop too, but I doubt there would be a TLE for that case, basically they wanted to understand if we get this little catch or not. Cause we should always try to go for the most optimal option when it comes to Traversal in a string, this type of problem often comes in inputs of 10^9 order.

I feel that for such kind of problems going with C++ is a better option bcz as it is we won't be able to get any benefit of the built in features of Python like the Counter function and also the while loop in Python is slow as hell, so it would always be a better choice to go with C++.

Problem Statement:-

Consider a string $�$ consisting of lowercase Latin alphabets.
In one operation, you can pick an index from string $�$ and replace the character at that index with $3$ occurrences of the same character.
For example, if $�=\mathtt{\text{dabc}}$, in one operation, we can choose the index $2$ and replace ${�}_2$ with $3$ occurrences of ${�}_2$. Thus, the string becomes $�=\mathtt{\text{d}}\underset{‾}{\mathtt{\text{aaa}}}\mathtt{\text{bc}}$.

Chefina has a string $�$ of length $�$.
Help Chef design a string $�$ of minimum length such that Chef can convert it to $�$ using any (possibly zero) number of operations.

It is guaranteed that exactly one such $�$ exists.

Input Format

• The first line of input contains a single integer $�$, the number of test cases.
• Each test case consists of multiple lines of input.
  • The first line of each test case consists of an integer $�$ — the length of the string $�$.
  • The next line consists of string $�$.

Output Format

For each test case, output on a new line, the string $�$ of minimum length, such that Chef can convert it to $�$ using any (possibly zero) number of operations.

Constraints

• $1\le �\le 10^4$
• $1\le �\le 10^6$
• $�$ consists of lowercase Latin alphabets only.
• The sum of $�$ over all test cases won't exceed $10^6$.

Sample 1:

Input

Output

3
6
aaabbb
7
abbbbbc
4
abcd

ab
abc
abcd

Explanation:

Test case $1$: With $�$ as $\mathtt{\text{ab}}$, we can first replace $\underset{‾}{\mathtt{\text{a}}}\mathtt{\text{b}}$ with $\underset{‾}{\mathtt{\text{aaa}}}\mathtt{\text{b}}$, and then $\mathtt{\text{aaa}}\underset{‾}{\mathtt{\text{b}}}$ with $\mathtt{\text{aaa}}\underset{‾}{\mathtt{\text{bbb}}}$.
We cannot construct $�$ from a string having length less than $2$.

Test case $2$: With $�$ as $\mathtt{\text{abc}}$, we can first replace $\mathtt{\text{a}}\underset{‾}{\mathtt{\text{b}}}\mathtt{\text{c}}$ with $\mathtt{\text{a}}\underset{‾}{\mathtt{\text{bbb}}}\mathtt{\text{c}}$, and then $\mathtt{\text{ab}}\underset{‾}{\mathtt{\text{b}}}\mathtt{\text{bc}}$ with $\mathtt{\text{ab}}\underset{‾}{\mathtt{\text{bbb}}}\mathtt{\text{bc}}$.

Test case $3$: Here $�=\mathtt{\text{abcd}}$, and no operations need to be applied.
We cannot construct $�$ from a string having length less than $4$.

Code Implementation:-

C++17

 #include <bits/stdc++.h>

using namespace std;

 

int main() {

    int t;

    cin>>t;

    while(t--){

            int n;

            cin>>n;

            string s;

            cin>>s;

           

            string answer="";

            int i=0;

           

            // Using while loop so I can directly hop to the next new element after the contiguous same elems

            while(i<n){

                // j will iterate through next elems uptill the same elem(ith elem) is being repeated to get it's frequency

                // count will store the frequency of the ith elem

                int j=i+1,count=1;

                while(j<n){

                    if(s[j]==s[i]){

                        count++;

                    }

                    else{

                        // If we get a new element, so we will just break out of the loop

                        break;

                    }

                    j++;

                }

                // If we see the pattern, then we understand that for odd frequency elems, only 1 elem is required

                // but for even freq elems 2 elems are atleast required

                if(count%2==0){

                    // Getting 2 occurences of elem, for even freq.

                    answer+=s[i];

                    answer+=s[i];

                }

                else{

                    // 1 occurence for odd freq.

                    answer+=s[i];

                }

                // Will directly move to the next new elem(jth elem)

                i=j;

            }

           

            /* Nootan Stuff */

            // map<char,int>m;

            // for(int i=0;i<n;i++){

            //     m[s[i]]++;

            // }

            // string ans=" ";

            // for(auto x:m){

            //     cout<<x.first<<" "<<x.second<<", ";

            // }

            // cout<<"\n";

            // for(auto i:m){

            //     // if(i.second<3 || i.second%2==0){

            //     if(i.second%2==0){

            //         // while(i.second!=0){

            //             ans=ans+i.first+i.first;

            //             // i.second--;

            //     // }

                   

            //     }

               

            //     // else if(i.second>=3 and i.second%2==1){

            //     else if(i.second%2==1){

               

            //         ans=ans+i.first;

            //     }

            // }

            // cout<<ans<<endl;

            // cout<<"Hello?"<<endl;

            cout<<answer<<endl;

    }

    return 0;

}

Python3:-

for i in range(int(input())):

    n=int(input())

    u=input()

    d1=dict(ct(u))

    s1=""

    i=0

    # for i,c in enumerate(u):

    while(i<n):

        c=u[i]

        count=1

        # for j in range(i+1,n):

        j=i+1

        while(j<n):

            if(c==u[j]):

                count+=1

            else:

                break

            j+=1

        if(count%2==0):

            s1+=f"{c}{c}"

        else:

            s1+=c

        if(count==1):

            i+=1

        else:

            i=j

    # for ch,fr in d1.items():

    #     if(fr%2==0):

    #         s1+=f"{ch}{ch}"

    #     else:

    #         s1+=ch

    # print("".join(sorted(s1)))

    print(s1)

    # print(d1)

    # ls=list(u)

    # print(*sorted(set(ls)),sep="")

Explanation:-

Simply, the only logic in this problem is that we need to get the minimum possible occurrence of every element and according to the circumstance that an elem can be replaced by 3 of its occurrence, means 1 elem can be made to -->3,5,7,9,11,13... and so on, but what about the even freq elems, so that can be replaced by 2 of their occurrences, bcz 2 elems can be increased in the order--> 4,6,8,10,12,14... So, we just need to use this idea and replace even freq elems with 2 elems and odd freq elems with 1 elem. But there's a catch here, we cannot directly get the frequency of all elems, means in such a string --> "aaaabbbaaa", we will have to find the freq of elem a differently for both of its occurrences, we cannot directly consider it to be 7 as a whole, this was a mistake that I did for making use of the Counter in Python and was getting the WA for many Test Cases, apart from that the problem was kinda medium level.