Question: Capgemini, Recent Online Assessment(OA) Questions | Dream String | Feb 2025

Entering edit mode

Problem Statement: Dream String

You are given a string S of length N. Your task is to determine and print the minimum number of operations required to convert S into a Dream string.

A Dream string consists only of vowels.

In an operation, you select an index i in S and increment S[i] to the next character cyclically. That is, 'a' becomes 'b', 'b' becomes 'c', and so on, and 'z' becomes 'a'.

Note:

If S is already a Dream string, print 0.
The vowels are 'a', 'e', 'i', 'o', and 'u'.
It is guaranteed that any string can be converted to a Dream string using a finite number of operations.

Input Format:

The input consists of two lines:

The first line contains a single integer N—the length of the string S.
The second line contains a single string S.

Output Format:

Print one number—the minimum number of operations required to convert string S into a Dream string.

ADD COMMENT • link

Entering edit mode

Dream String Solution

Topics Involved / Prerequisites

String Traversal
Modular Arithmetic (ASCII Math)
Greedy Approach

Overview

To minimize the total operations, we must independently change each character to its nearest forward-reachable vowel in the alphabet. Since the increment operation wraps around from 'z' to 'a', the distance must account for this cyclic nature using basic math. By summing the minimum forward cyclic distance to any vowel for every character, we guarantee the absolute minimum total operations.

Approach

1. Calculating Cyclic Distance Because we can only increment letters forward, calculating the distance between a character and a vowel requires two scenarios. If the vowel's ASCII value is greater than or equal to our character (e.g., 'b' to 'e'), the distance is simply vowel - character. If the vowel is alphabetically behind our character (e.g., 'y' to 'a'), we must wrap around the alphabet, making the distance vowel - character + 26.

2. Finding the Optimal Vowel For each character in the string, we don't know immediately which vowel is "closest" going forward. We simply loop through a fixed list of all five vowels (a, e, i, o, u), calculate the cyclic distance to each, and select the smallest value. We add this smallest value to a running total to get our final answer.

function getCyclicDistance(currentChar, targetVowel):
    dist = targetVowel - currentChar
    
   
    if dist < 0:
        dist = dist + 26
        
    return dist

function minOperationsToDreamString(n, s):
    vowels = ['a', 'e', 'i', 'o', 'u']
    totalOperations = 0
    
    for i from 0 to n - 1:
        minSteps = infinity
  
        for each v in vowels:
            steps = getCyclicDistance(s[i], v)
            minSteps = min(minSteps, steps)
            
        // Add the absolute shortest path to our total
        totalOperations = totalOperations + minSteps
        
    return totalOperations

Time Complexity

Time: O(N) - For each of the N characters, we perform exactly 5 checks (one for each vowel), meaning the time scales linearly with the string length.
Space: O(1) - We only use a constant-sized array to store the vowels and a few variables for tracking the sum.

ADD REPLY • link 16 days ago

admin 1.9k