#PROBLEM LINK:
Author: Chandan Boruah
Tester: Chandan Boruah
Editorialist: Chandan Boruah
#DIFFICULTY:
EASY
#PREREQUISITES:
Maths
#PROBLEM:
Given a string sort it only by taking characters and moving them to the right correct position, towards the right end of the string. Find minimum number of moves needed to sort the string.
#QUICK EXPLANATION:
The moves will be minimum if the largest ascii character is put to the right position first then the second largest and so on, starting from the right move to the left finding characters larger than already found. For every character update an array containing 26 integers representing the 26 english alphabets.
#EXPLANATION:
The moves will be minimum if the largest ascii character is put to the correct position first then the second largest and so on. Starting from the right move to the left finding characters larger than already found. For every character update an array containing 26 integers representing the 26 english alphabets. If the character is smaller than the character in the array then increment the value by 1. To put the current unsorted character in the end, the total number of moves needed would be the current number of characters to the right.
Creating new strings wouldn’t work cause of the constraints.
#AUTHOR’S AND TESTER’S SOLUTIONS:
using System;
using System.Collections.Generic;
class some
{
public static void Main()
{
string s=Console.ReadLine();
int[]arr=new int[26];
int count=0;
for(int i=s.Length-1;i>=0;i--)
{
int thiscount=0;
int num=int.Parse(""+(s[i]-'a'));
for(int j=0;j<26;j++)
{
if(j<num && arr[j]!=0)thiscount=arr[j];
if(j>num && arr[j]!=0)
arr[j]++;
}
arr[num]=thiscount+1;
count+=thiscount;
}
Console.WriteLine(count);
}
}