A. Reverse a Substring | Codeforces Solution | Educational Codeforces Round 63 (Rated for Div. 2)

You are given a string 𝑠 consisting of 𝑛 lowercase Latin letters. Let's define a substring as a contiguous subsegment of a string. For example, "acab" is a substring of "abacaba" (it starts in position 3 and ends in position 6 ), but "aa" or "d" aren't substrings of this string. So the substring of the string 𝑠 from position 𝑙 to position 𝑟 is 𝑠[𝑙;𝑟]=𝑠𝑙𝑠𝑙+1…𝑠𝑟 . You have to choose exactly one of the substrings of the given string and reverse it (i. e. make 𝑠[𝑙;𝑟]=𝑠𝑟𝑠𝑟−1…𝑠𝑙 ) to obtain a string that is less lexicographically. Note that it is not necessary to obtain the minimum possible string.

A. Reverse a Substring

time limit per test: 2 seconds
memory limit per test: 256 megabytes

You are given a string s consisting of n lowercase Latin letters.

Let's define a substring as a contiguous subsegment of a string. For example, "acab" is a substring of "abacaba" (it starts in position 3 and ends in position 6), but "aa" or "d" aren't substrings of this string. So the substring of the string s from position l to position r is s[l;r] = s_ls_l+1…s_r.

You have to choose exactly one of the substrings of the given string and reverse it (i. e. make s[l;r] = s_rs_r−1…s_l) to obtain a string that is less lexicographically. Note that it is not necessary to obtain the minimum possible string.

If it is impossible to reverse some substring of the given string to obtain a string that is less, print "NO". Otherwise print "YES" and any suitable substring.

String x is lexicographically less than string y, if either x is a prefix of y (and x ≠ y), or there exists such i (1 ≤ i ≤ min(|x|, |y|)), that x_i < y_i, and for any j (1 ≤ j < i) x_j = y_j. Here |a| denotes the length of the string a. The lexicographic comparison of strings is implemented by operator < in modern programming languages.

Input

The first line of the input contains one integer n (2 ≤ n ≤ 3⋅10⁵) — the length of s.

The second line of the input contains the string s of length n consisting only of lowercase Latin letters.

Output

If it is impossible to reverse some substring of the given string to obtain a string which is lexicographically less, print "NO". Otherwise print "YES" and two indices l and r (1 ≤ l < r ≤ n) denoting the substring you have to reverse. If there are multiple answers, you can print any.

Example

Input

7
abacaba

Output

YES
2 5

Input

6
aabcfg

Output

NO

Note

In the first testcase the resulting string is "aacabba".

Solution

The problem requires us to find a substring in the given string s that, when reversed, results in a string lexicographically smaller than the original. Here's the solution approach:

Key Insight:
- A string becomes lexicographically smaller if, after reversing a substring, at least one character at an earlier position becomes smaller than it was in the original string, while all characters before it remain unchanged or compatible with being a prefix.
- We only need to find a substring where reversing it produces a smaller string—any valid case will do.
Observation:
- If there exists a pair of adjacent characters s[i] and s[i+1] where s[i] > s[i+1], reversing the substring from i to i+1 (length 2) will swap them, making the string smaller.
- For example, in "ba", reversing to "ab" makes it lexicographically smaller because 'a' < 'b' at the first position.
- This works because swapping a larger character with a smaller one earlier in the string reduces its lexicographic order.
Algorithm:
- Iterate through the string from index 0 to n-2.
- For each position i, check if s[i] > s[i+1].
- If true, reversing the substring from i+1 to i+2 (1-based indexing) will make the string smaller.
- Output "YES" and the indices i+1 and i+2, then stop.
- If no such pair is found after checking all positions, output "NO".
Why Adjacent Pairs Suffice:
- We don’t need to reverse a longer substring because any substring that can be reversed to make the string smaller must contain at least one position where the original order decreases (i.e., a larger character followed by a smaller one).
- Finding and reversing just that pair is enough to satisfy the condition.
Time Complexity:
- O(n) for a single pass through the string.

Example Walkthrough:

Input: "abacaba" (n = 7)
Check pairs:
- s[0] = 'a', s[1] = 'b': 'a' < 'b', no swap.
- s[1] = 'b', s[2] = 'a': 'b' > 'a', swap possible.
Reverse s[1..2] (indices 2 to 5 in 1-based): Original "abacaba" → Reverse "baca" (positions 2-5) → Result "aacabba".
"aacabba" < "abacaba" (at position 2, 'a' < 'b'), so output "YES 2 5".
Input: "aabcfg" (n = 6)
Check pairs: All adjacent pairs are non-decreasing ('a' = 'a', 'a' < 'b', 'b' < 'c', 'c' < 'f', 'f' < 'g').
No pair where s[i] > s[i+1], so output "NO".

Sample Code:

int n; cin >> n;
string s; cin >> s;
for (int i = 0; i < n-1; i++) {
    if (s[i] > s[i+1]) {
        cout << "YES\n" << i+1 << " " << i+2 << endl;
        return;
    }
}
cout << "NO\n";

void solve()
{
  int n;
  cin >> n;
  string s;
  cin >> s;

  for (int i = 1; i < n; i++)
  {
    if (s[i] < s[i - 1])
    {
      cout << "YES\n";
      cout << i << " " << i + 1 << endl;
      return;
    }
  }

  cout << "NO\n";
}


#include <bits/stdc++.h>

using namespace std;

#define int long long int
#define F first
#define S second
#define pb push_back
#define si set<int>
#define vi vector<int>
#define pii pair<int, int>
#define vpi vector<pii>
#define vpp vector<pair<int, pii>>
#define mii map<int, int>
#define mpi map<pii, int>
#define spi set<pii>
#define endl "\n"
#define sz(x) ((int)x.size())
#define all(p) p.begin(), p.end()
#define double long double
#define que_max priority_queue<int>
#define que_min priority_queue<int, vi, greater<int>>
#define bug(...) __f(#__VA_ARGS__, __VA_ARGS__)
#define print(a)      \
  for (auto x : a)    \
    cout << x << " "; \
  cout << endl
#define print1(a)  \
  for (auto x : a) \
  cout << x.F << " " << x.S << endl
#define print2(a, x, y)       \
  for (int i = x; i < y; i++) \
    cout << a[i] << " ";      \
  cout << endl
#define scanit(a, n)                           \
  for (ll indexaa = 0; indexaa < n; indexaa++) \
    cin >> a[indexaa];

inline int power(int a, int b)
{
  int x = 1;
  while (b)
  {
    if (b & 1)
      x *= a;
    a *= a;
    b >>= 1;
  }
  return x;
}

template <typename Arg1>
void __f(const char *name, Arg1 &&arg1) { cout << name << " : " << arg1 << endl; }
template <typename Arg1, typename... Args>
void __f(const char *names, Arg1 &&arg1, Args &&...args)
{
  const char *comma = strchr(names + 1, ',');
  cout.write(names, comma - names) << " : " << arg1 << " | ";
  __f(comma + 1, args...);
}

const int N = 200005;

void solve()
{
  int n;
  cin >> n;
  string s;
  cin >> s;

  for (int i = 1; i < n; i++)
  {
    if (s[i] < s[i - 1])
    {
      cout << "YES\n";
      cout << i << " " << i + 1 << endl;
      return;
    }
  }

  cout << "NO\n";
}

int32_t main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);

  clock_t z = clock();

  int t = 1;
  //   cin >> t;
  while (t--)
    solve();

  return 0;
}

TagsA. Reverse a SubstringEducational Codeforces Round 63 (Rated for Div. 2)

Raunit Verma

Technical Writer at CodingKaro

Share this on