[Solved] find the minimum swaps required to make string beautiful GFG Contest

Minimum Swaps: Geek has a string S consisting of lowercase english alphabet characters. Geek wants string to look beautiful which is only possible when all the vowels present in the string forms a consecutive chain of characters in the string. Your task is to find the minimum swaps required to make string beautiful.

Example 1:

Input:
S = "ababab"

Output:
1

Explanation:
We will swap second character of the
string with fifth character of the string
which will make string beautiful.

Example 2:

Input:
S = "aaabbb"

Output:
0
Explanation:
The string is already beautiful.

Your Task:
You don't need to read input or print anything. Your task is to complete the function minSwaps( ) which takes string S as an input parameter and returns the number of minimum swaps required.

Expected Time Complexity: O(|S|)
Expected Auxiliary Space: O(|S|)

Constraints:
1 ≤ |S| ≤ 2*105

Solution

def minSwaps(self,s):

    size = len(s)
    arrpos = [*enumerate(s)]
    arrpos.sort(key=lambda x: x[1])
    vis = {k: False for k in range(size)}
    ans = 0
    for i in range(size):
        if vis[i] or arrpos[i][0] == i:
            continue
        j = i
        while not vis[j]:
            vis[j] = True
            j = arrpos[j][0]
        ans += 1
    return ans

Happy Learning – If you require any further information, feel free to contact me.