Vowel Shift Cipher — Problem Statement & Solution Guide

StringsMediumMixed

TimeO(n)

SpaceO(1)

Quick Answer & Algorithm Key Takeaway

Master coding challenges related to Strings and solve the Vowel Shift Cipher problem optimally.

TopicStrings

PatternMixed

TimeO(n)

SpaceO(1)

Problem Description

Given a lowercase English string s, replace each vowel with the next vowel in the cyclic order a→e→i→o→u→a, leaving all consonants unchanged. After completing the substitution, reverse the entire string and output the resulting string. The function should run in linear time relative to the length of s.

DSA Pattern Breakdown

"Vowel Shift Cipher"

medium

WHY DOES IT MATTER?

The pattern teaches how to combine element‑wise transformations with a global reordering while preserving linear performance, a frequent requirement in text processing pipelines and encoding/decoding tasks.

OPTIMIZATION CHALLENGE

Recognizing that the vowel mapping is a constant‑size lookup allows O(1) per‑character work, and that reversal can be done by swapping indices rather than building a new string, collapsing two logical steps into two simple passes.

REAL-WORLD CONNECTION

Think of a network packet that must be encrypted (byte‑wise substitution) and then sent in reverse order to satisfy a protocol’s end‑to‑end checksum; both steps must be fast and memory‑light to keep latency low.

During an interview, implement the mapping as a static array indexed by character code; this avoids conditionals and makes the code both faster and cleaner, and it signals that you think about constant‑time lookups.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(1)

Core Theory — Why This Approach?

The problem combines two linear‑time string transformations: a character‑wise substitution based on a fixed cyclic mapping of vowels, and a full reversal of the resulting sequence. A naïve solution might first build a new string by scanning the input, performing the vowel shift, and then call a library reverse function; both steps are O(n) and together still O(n), but the key is to avoid extra passes or auxiliary containers that increase space. The optimal paradigm is to treat the string as an array of characters and perform the substitution in‑place (or in a single output buffer) while simultaneously preparing for the reversal, which can be done in a second pass that swaps symmetric positions. This two‑pass, constant‑extra‑space approach guarantees linear time and O(1) auxiliary space, which is essential when n can be up to 10⁶ or more, where any super‑linear overhead would cause time‑outs or memory pressure.

Interview Questions on This Problem

Q1How would you modify the solution if the vowel cycle were a→i→u→e→o→a instead of the standard order?

Create a lookup table (e.g., a dictionary or array) that maps each vowel to its successor in the new cycle, then reuse the same linear scan and reversal logic; the change is isolated to the mapping, not the algorithmic structure.

Q2What is the time and space complexity if you used string concatenation inside the loop instead of a mutable buffer?

Each concatenation creates a new string, leading to O(n²) time due to repeated copying, and O(n²) total allocated memory, which is unacceptable for large inputs.

Q3In a distributed system processing massive logs, how could you parallelize the vowel‑shift‑and‑reverse operation?

Partition the input into chunks, apply the vowel shift locally, then reverse each chunk; finally, reorder the chunks in reverse order and, for the boundary between chunks, perform a final in‑place reversal of the concatenated result to maintain global order.

Examples

Example 1

Input

hello

Output

allih

Explanation: Original: h e l l o → shift vowels: e→i, o→a → "hilla" → reverse → "allih".

Example 2

Input

algorithm

Output

mhtorugle

Explanation: Original: a l g o r i t h m → shift vowels: a→e, o→u, i→o → "elgurothm" → reverse → "mhtorugle".

Example 3

Input

aeiou

Output

auoie

Explanation: Original: a e i o u → shift vowels: a→e, e→i, i→o, o→u, u→a → "eioua" → reverse → "auoie".

Constraints

1 <= s.length <= 100000
s contains only lowercase English letters

Optimal Approach & Strategy

Use a constant‑time lookup table for vowel shifts and write results into a pre‑allocated char array, then reverse the array in‑place with two‑pointer swaps, achieving O(n) time and O(1) extra space.

Brute Force Approach

Iterate over the string, build a new string with vowel replacements using concatenation, then call a built‑in reverse that creates another copy; this results in O(n²) time due to repeated copying.

Code Solutions

Language:

JavaScript Solution

Time: O(n)

function vowelShiftCipher(s) {
    const vowels = "aeiou";
    const shiftedVowels = "eioua";
    
    let result = "";
    for (let i = 0; i < s.length; i++) {
        const c = s[i];
        const pos = vowels.indexOf(c);
        if (pos !== -1) {
            result += shiftedVowels[pos];
        } else {
            result += c;
        }
    }
    
    return result.split('').reverse().join('');
}

// Driver code
const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    terminal: false
});

rl.on('line', (line) => {
    const s = line.trim();
    console.log(vowelShiftCipher(s));
    rl.close();
});

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

string vowelShiftCipher(string s) {
    string vowels = "aeiou";
    string shiftedVowels = "eioua";
    
    for (char &c : s) {
        size_t pos = vowels.find(c);
        if (pos != string::npos) {
            c = shiftedVowels[pos];
        }
    }
    
    reverse(s.begin(), s.end());
    return s;
}

int main() {
    string s;
    cin >> s;
    cout << vowelShiftCipher(s) << endl;
    return 0;
}

import java.util.Scanner;

public class Main {
    public static String vowelShiftCipher(String s) {
        String vowels = "aeiou";
        String shiftedVowels = "eioua";
        
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            int pos = vowels.indexOf(c);
            if (pos != -1) {
                sb.append(shiftedVowels.charAt(pos));
            } else {
                sb.append(c);
            }
        }
        
        return sb.reverse().toString();
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.next();
        System.out.println(vowelShiftCipher(s));
        scanner.close();
    }
}

def vowel_shift_cipher(s: str) -> str:
    vowels = "aeiou"
    shifted_vowels = "eioua"
    
    result = []
    for c in s:
        pos = vowels.find(c)
        if pos != -1:
            result.append(shifted_vowels[pos])
        else:
            result.append(c)
    
    return ''.join(result[::-1])

if __name__ == "__main__":
    s = input().strip()
    print(vowel_shift_cipher(s))

function vowelShiftCipher(s) {
    const vowels = "aeiou";
    const shiftedVowels = "eioua";
    
    let result = "";
    for (let i = 0; i < s.length; i++) {
        const c = s[i];
        const pos = vowels.indexOf(c);
        if (pos !== -1) {
            result += shiftedVowels[pos];
        } else {
            result += c;
        }
    }
    
    return result.split('').reverse().join('');
}

// Driver code
const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    terminal: false
});

rl.on('line', (line) => {
    const s = line.trim();
    console.log(vowelShiftCipher(s));
    rl.close();
});

Asked in Top Tech Interviews

Uber

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.