Logo

Kode$word

Reverse Vowels of a String – From Extra Space Approach to Two Pointer Optimization (LeetCode 345)
Reverse Vowels of a String – From Extra Space Approach to Two Pointer Optimization (LeetCode 345)

Reverse Vowels of a String – From Extra Space Approach to Two Pointer Optimization (LeetCode 345)

Understanding Different Ways to Reverse Only Vowels Efficiently

21 views
0
0
Two PointersString ManipulationHashMapLeetCodeEasy
Github icon

🔗 Problem Link

LeetCode 345 – Reverse Vowels of a String

👉 https://leetcode.com/problems/reverse-vowels-of-a-string/

Introduction

This problem is very similar to Reverse Only Letters, but with a small twist:

Instead of reversing all letters, we only reverse the vowels.

At first, we might think of extracting vowels, reversing them, and putting them back. That works — but it is not the most optimal approach.

In this article, we’ll:

  1. Understand the brute-force style approach (your solution)
  2. Analyze its time complexity
  3. Optimize it using the Two Pointer pattern
  4. Compare both approaches

📌 Problem Understanding

You are given a string s.

You must:

  1. Reverse only the vowels
  2. Keep all other characters in the same position

Vowels include:

a, e, i, o, u
A, E, I, O, U

Example 1

Input: "IceCreAm"
Output: "AceCreIm"

Vowels: ['I','e','e','A']

Reversed: ['A','e','e','I']

Example 2

Input: "leetcode"
Output: "leotcede"

🧠 Your First Approach – Extract, Reverse, Replace

Your idea:

  1. Extract all vowels into a string.
  2. Store their indices.
  3. Reverse the vowel string.
  4. Replace vowels at stored indices.

Let’s look at your code.

💻 Your Code (Extract & Replace Method)

class Solution {
public String reverseVowels(String s) {
String vow = "";
List<Integer> lis = new ArrayList<>();
HashMap<Integer,Character> mp = new HashMap<>();

for(int i =0;i<s.length();i++){
if(((s.charAt(i) == 'a') || (s.charAt(i) == 'e') ||
(s.charAt(i) == 'i') || (s.charAt(i) == 'o') ||
(s.charAt(i) == 'u') || (s.charAt(i) == 'A') ||
(s.charAt(i) == 'E') || (s.charAt(i) == 'I') ||
(s.charAt(i) == 'O') || (s.charAt(i) == 'U')) ){
vow += s.charAt(i);
lis.add(i);
}
}

String so = "";
for(int i = vow.length()-1; i >= 0; i--){
so += vow.charAt(i);
}

for(int i =0; i< lis.size();i++){
mp.put(lis.get(i), so.charAt(i));
}

String ans = "";
for(int i =0 ; i< s.length();i++){
if(mp.containsKey(i)){
ans += mp.get(i);
}else{
ans += s.charAt(i);
}
}

return ans;
}
}

🔍 How This Works

Step 1 – Extract Vowels

Store:

  1. Vowel characters in vow
  2. Their indices in lis

Step 2 – Reverse the Vowel String

Create new reversed string so.

Step 3 – Map Indices to Reversed Vowels

Use a HashMap to store:

index → reversed vowel

Step 4 – Build Final String

Traverse original string:

  1. If index in map → use reversed vowel
  2. Else → use original character

⚠️ Problem with This Approach

Although correct, it has inefficiencies:

  1. String concatenation (+=) → O(n²) in worst case
  2. Extra space used:
  3. Vowel string
  4. List of indices
  5. HashMap
  6. Final answer string

Time Complexity: O(n²) (due to string concatenation)

Space Complexity: O(n)

We can do better.

🚀 Optimized Approach – Two Pointers (Best Solution)

Instead of extracting vowels separately, we can:

  1. Convert string into char array
  2. Use two pointers
  3. Swap vowels directly

This avoids extra structures.

💻 Optimized Two Pointer Solution

class Solution {
public String reverseVowels(String s) {
int i = 0, j = s.length() - 1;
char[] arr = s.toCharArray();

while(i < j){
if(!isVowel(arr[i])){
i++;
}
else if(!isVowel(arr[j])){
j--;
}
else{
char temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
}

return new String(arr);
}

private boolean isVowel(char c){
return c=='a'||c=='e'||c=='i'||c=='o'||c=='u'||
c=='A'||c=='E'||c=='I'||c=='O'||c=='U';
}
}

🎯 Why This Works

We:

  1. Move left pointer until vowel found
  2. Move right pointer until vowel found
  3. Swap
  4. Continue

No extra storage needed.

⏱ Complexity Comparison

Your Approach

  1. Time: O(n²) (string concatenation)
  2. Space: O(n)

Two Pointer Approach

  1. Time: O(n)
  2. Space: O(n) (char array)

Much cleaner and faster.

🔥 Key Learning

This problem reinforces:

  1. Two pointer pattern
  2. In-place modification
  3. Avoiding unnecessary extra space
  4. Recognizing optimization opportunities

Whenever you see:

"Reverse something but keep other elements fixed"

Think:

👉 Two Pointers

🏁 Final Thoughts

Your approach shows strong logical thinking:

  1. Extract → Reverse → Replace

That’s a valid way to solve it.

But the optimized two-pointer approach is more interview-friendly.

If you master this pattern, you can easily solve:

  1. Reverse Only Letters
  2. Reverse String
  3. Valid Palindrome
  4. Remove Duplicates from Sorted Array

Related Articles

Reverse Only Letters – Two Pointer Strategy Explained (LeetCode 917)

Reverse Only Letters – Two Pointer Strategy Explained (LeetCode 917)

Reversing Letters While Preserving Special Characters in Place

Read Article
Check if All Characters Have Equal Number of Occurrences – Frequency Map Approach (LeetCode 1941)

Check if All Characters Have Equal Number of Occurrences – Frequency Map Approach (LeetCode 1941)

Simple HashMap Technique to Validate Equal Character Frequencies

Read Article
Find the Difference – Smart ASCII Sum Trick (LeetCode 389)

Find the Difference – Smart ASCII Sum Trick (LeetCode 389)

Solving the Problem Using Character Arithmetic Instead of Extra Space

Read Article
Ransom Note – Frequency Counting Made Simple (LeetCode 383)

Ransom Note – Frequency Counting Made Simple (LeetCode 383)

Using HashMap to Validate Character Availability Efficiently

Read Article

Ai Assistant Kas