Google Kick Start 2021 Round H - C(Silly Substitutions)

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

int main() {
	int T;
	scanf("%d", &T);
	
	for(int tc = 1; tc <= T; tc++) {
		int N;
		scanf("%d", &N);
		char S[555555];
		scanf("%s", S);
		vector<int> s(N);
		for(int i = 0; i < N; i++)
			s[i] = (int)(S[i])-48;
		
		vector<set<int>> interesting(10);
		vector<int> next(N); for(int i = 0; i < N-1; i++) next[i] = i+1; next[N-1] = -1;
		vector<int> prev(N); for(int i = 0; i < N; i++) prev[i] = i-1;
		for(int i = 0; i < N-1; i++) {
			if((s[i]+1)%10 == s[i+1])
				interesting[s[i]].insert(i);
		}
		while(interesting[0].size() + interesting[1].size() + interesting[2].size() + interesting[3].size() + interesting[4].size() + interesting[5].size() + interesting[6].size() + interesting[7].size() + interesting[8].size() + interesting[9].size() > 0) {			
			for(int i = 0; i < 10; i++) {
				for(auto it = interesting[i].begin(); it != interesting[i].end(); it++) {
					int cur = *it;
					s[cur] = (i+2)%10;
					interesting[(i+1)%10].erase(next[cur]);
					if(cur != 0)
						interesting[(i+9)%10].erase(prev[cur]);
					next[cur] = next[next[cur]];
					if(next[cur] != -1)
						prev[next[cur]] = cur;
					if(cur != 0) {
						if(s[prev[cur]] == (i+1)%10)
							interesting[(i+1)%10].insert(prev[cur]);
					}
					if(next[cur] != -1) {
						if(s[next[cur]] == (i+3)%10)
							interesting[(i+2)%10].insert(cur);
					}
				}
				if(interesting[i].size() > 0)
					interesting[i].clear();
			}
		}
		printf("Case #%d: ", tc);
		int cur = 0;
		while(cur != -1) {
			printf("%d", s[cur]);
			cur = next[cur];
		}
		printf("\n");
	}
}