Code : Nearly Shortest Repeating Substring

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

bool is_almost_equal(string &lhs, string &rhs) {
    if (rhs.length() != rhs.length()) {
        return false;
    }
    int mismatch = 0;
    for (int i = 0; i < (int)lhs.length(); i++) {
        if (lhs[i] != rhs[i]) {
            mismatch++;
        }
    }
    return mismatch <= 1;
}

int solve(string &str) {
    int n = str.length();
    vector<int> div;
    for (int i = 1; i <= sqrt(n); i++) {
        if (n % i == 0) {
            div.push_back(i);
            div.push_back(n / i);
        }
    }
    sort(div.begin(), div.end());

    for (auto &d : div) {
        vector<string> choices = {str.substr(0, d), str.substr(n - d, d)};
        for (auto &part : choices) {
            string created;
            while (created.length() != str.length()) {
                created += part;
            }
            if (is_almost_equal(str, created)) {
                return d;
            }
        }
    }
    return n;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    for (int zz = 0; zz < t; zz++) {
        int n;
        cin >> n;
        string str;
        cin >> str;
        cout << solve(str) << "\n";
    }
    return 0;
}