B. pspspsps|Codeforces Round 994 (Div. 2)||c++ solution 100% test case pass

[@Code-Review-c91]

#include #include #include #include using namespace std; bool solve(int n, string &s) { vector p(n, INT_MAX); // To store the prefix minimum for 'p' vector s_arr(n, INT_MAX); // To store the suffix minimum for 's' // Step 1: Assign values for 'p' and 's' for (int i = 0; i < n; ++i) { if (s[i] == 'p') { p[i] = i + 1; // p[i] should be i + 1 (1-based index) } if (s[i] == 's') { s_arr[i] = n - i; // s[i] should be n - i } } // Step 2: Propagate forward in s_arr to ensure suffix min constraint for (int i = 1; i < n; ++i) { s_arr[i] = min(s_arr[i], s_arr[i - 1]); } // Step 3: Propagate backward in p to ensure prefix min constraint for (int i = n - 2; i >= 0; --i) { p[i] = min(p[i], p[i + 1]); } // Step 4: Create the temp array with the minimum of p[i] and s_arr[i] vector temp(n); for (int i = 0; i < n; ++i) { temp[i] = min(s_arr[i], p[i]); } // Step 5: Sort the temp array vector sorted_temp = temp; sort(sorted_temp.begin(), sorted_temp.end()); // Step 6: Check if sorted_temp[i] >= i + 1 for all i for (int i = 0; i < n; ++i) { if (sorted_temp[i] < i + 1) { return false; // If any element fails the condition, return false } } return true; } int main() { int t; cin >> t; // Read number of test cases while (t--) { int n; string s; cin >> n >> s; // Read n and the string s if (solve(n, s)) { cout