Codeforces Round 862 (Div. 2) - B. The String Has a Target (800)

B. The String Has a Target

가장 작은 문자의 가장 뒤에 있는 인덱스를 골라주면 된다.

일단 가장 작은 문자를 골라야 하는 이유는 항상 가장 작은 문자가 가장 먼저 앞에 나오게 만들어줄 수 있기 때문이다.

가장 작은 문자들 중 가장 뒤의 것을 골라야 하는 이유는 다음과 같다.

가장 작은 문자가 나오는 인덱스를 $i_1, i_2, \cdots (i_1 < i_2 < \cdots )$ 라 하자.

$i_1$을 제일 앞으로 보낸다면 결과 문자열 $t$는 가장 작은 문자가 $a$ 이고 원본 문자열이 $s$라면

$t_1=as_{1,i_1-1}s_{i_1+1,n}$ 이 된다. $i_2$ 를 이용해 하면

$t_2=as_{1,i_2-1}s_{i_2+1,n}$ 이 된다.

잘 보면 prefix가 일치하다가 가장 먼저 문자가 달라지는 시점($i=i_1+1$)에 $t_2$ 에선 $a$ 가 나오고 $t_1$ 에선 그렇지 않다.

따라서 가장 뒤에 것을 제일 앞으로 보내는게 최적이다.

void solve() {
   int n;
   cin >> n;
   string s;
   cin >> s;
   vi mx(26, -1);
   for (int i = 0; i < n; i++) {
      maxa(mx[s[i] - 'a'], i);
   }
   auto get_sub = [&](int l, int r) -> string {
      if (l > r) return "";
      return s.substr(l, r - l + 1);
   };
   for (int i = 0; i < 26; i++) {
      if (mx[i] == -1) continue;
      cout << string(1, char(i + 'a')) + get_sub(0, mx[i] - 1) + get_sub(mx[i] + 1, n - 1) << endl;
      break;
   }
}