Problem 23: Minimum Adjacent Swaps to Group All Vowels
Problem Statement: Given a string, find the minimum number of adjacent swaps required to group all the vowels together. Only the positions of vowels matter.
Input
A single line containing the string (consisting of lowercase English letters).
Output
Print the minimum number of adjacent swaps needed.
Examples
Input:
abcdaeieo
Output:
5
Solution Explanation
Method 1: Record the positions of vowels and then choose a target segment where the vowels are contiguous. Calculate the cost by summing the distances between current positions and target positions. Method 2: Use a sliding window approach on the array of vowel positions to minimize total swaps required.
Solution in C++
#include
#include
#include
using namespace std;
bool isVowel(char c) {
return c=='a' || c=='e' || c=='i' || c=='o' || c=='u';
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s; getline(cin, s);
vector pos;
for (int i=0; i