Nasser's Concatenation#12479

Nasser's Concatenation (Editorial)

Problem Author:	Mohammad Nasser (MOAGEZA)
Prepared by:	Mohammad Nasser (MOAGEZA)
Edited by:	Hasan Saleh (MathModel)

Solution

General Idea: We need to find the maximum length of a uniform substring (all same character) across all possible orderings of the four strings.

Since there are only $4! = 24$ 4! = 24 possible permutations, we can try all of them.

For each permutation:

Concatenate the four strings in that order.
Find the longest contiguous substring of identical characters.
Track the maximum across all permutations.

To find the longest uniform substring in a string:

Iterate through the string.
Count consecutive identical characters.
Update the maximum when the character changes.

The key insight is that with only 4 strings and small constraints, brute force is efficient enough.

The solution runs in $O (4! \cdot n)$ \mathcal{O}(4! \cdot n) time per test case, which simplifies to $O (n)$ since $4! = 24$ 4! = 24 is a constant.

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

void solve() {
    int n;
    cin >> n;
    vector<string> v(4);
    
    for (int i = 0; i < 4; i++) {
        cin >> v[i];
    }
    
    int ans = 0;
    sort(v.begin(), v.end());
    
    do {
        string temp = "";
        for (int i = 0; i < 4; i++) {
            temp += v[i];
        }
        
        int cnt = 1;
        for (int i = 1; i < temp.size(); i++) {
            if (temp[i] == temp[i - 1]) {
                cnt++;
            } else {
                ans = max(ans, cnt);
                cnt = 1;
            }
        }
        ans = max(ans, cnt);
        
    } while (next_permutation(v.begin(), v.end()));
    
    cout << ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    int t;
    cin >> t;
    while (t--) {
        solve();
        cout << '\n';
    }
    return 0;
}