PROBLEM LINK:
Tester: Roman Bilyi
Editorialist: Hussain Kara Fallah
PROBLEM EXPLANATION
Saeed was teaching a string compression algorithm. This algorithm finds all maximal substrings which contains only one character repeated one or more times (a substring is maximal if it we cannot add one character to its left or right without breaking this property) and replaces each such substring by the string “cK”, where K is the length of the substring and c is the only character it contains. For example, “aabaaa” is compressed to “a2b1a3”.
Saeed wanted to check if the students understood the algorithm, so he wrote a string S on the board and asked the students if the algorithm is effective on S, i.e. if the string created by compressing S is strictly shorter than S. Help them answer this question.
DIFFICULTY:
Easy
CONSTRAINTS
1 \leq |N| \leq 10^6
EXPLANATION:
Now this is a straight forward implementation task. We need to perform the algorithm and check the length of the result.
First, let’s break our string into maximal contiguous substrings of identical characters. (a substring is maximal if we cannot extend it from left or right without breaking the identical characters property). We can do this by a simple loop.
Let’s keep 2 iterators. The first iterator always starts a new substring. Initially, it starts from the beginning of the string, now let’s move with our second iterator forward while we have identical characters (keeping their count as well). After we arrive at a new character, it means our substring is finished, and we move our first iterator to the character we stopped at (the new substring start) and we keep extracting substrings until our main string is exhausted.
Now for each processed substring, it would increase our compressed string length by F(substring\,length)+1 where F(x) is the length of integer x.
Let’s take an example “aabaaa”, it would be broken into “aa”,“b”,“aaa” so the length of compressed string would be F(2)+1+F(1)+1+F(3)+1=6.
After finishing we compare our compressed string length to the original and that’s it. Check implementation for better understanding.
Editorialist solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int T;
cin >> T;
while (T--) {
string str;
cin >> str;
int ans = 0;
for (int j = 0; j < str.size();) {
int i , l = 0;
for (i = j; i < str.size() && str[j] == str[i]; i++)
++l;
while(l > 0){
ans++;
l /= 10;
}
ans++;
j = i;
}
if (ans >= str.size()) puts("NO");
else puts("YES");
}
}
Tester Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int T;
cin >> T;
while (T--) {
string str;
cin >> str;
int ans = 0;
for (int j = 0; j < str.size();) {
int i , l = 0;
for (i = j; i < str.size() && str[j] == str[i]; i++)
++l;
while(l > 0){
ans++;
l /= 10;
}
ans++;
j = i;
}
if (ans >= str.size()) puts("NO");
else puts("YES");
}
}
