Prerequisites:- None
Problem :- Given a string T (without spaces) representing the mail. You can perform one of the following actions in each move:
Append a character at the end of the string.
Append a duplicate of the current string.
find the minimum number of moves needed to type the email.
Explanation :-
Begin by iterating through the string’s reverse.
At each position, determine if the string can be divided into two equal halves.
If division is possible, split the string into two halves and remove the second half.
If division is not possible, remove the last character of the string.
The logic behind this approach is to prioritize the removal of larger chunks. Identifying and removing larger substrings requires iterating from the reverse direction.
Solution :-
C++ Solution : -
#include <iostream>
using namespace std;
int main() {
// your code goes here
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
string s;
cin >> s;
int count = 0;
while (n > 0) {
if (s.substr(0, n / 2) == s.substr(n / 2, n - n / 2)) {
n = n / 2;
count++;
} else {
count++;
n--;
}
}
cout << count << endl;
}
return 0;
}