LeetCode Solution : Reverse Only Letters in a String in Kotlin

Reversing only the letters in a string while keeping all other characters in their original positions is an interesting problem that tests your ability to manipulate strings. In this post, we'll solve the LeetCode problem "Reverse Only Letters" step by step.

---

Problem Statement

Given a string s, reverse only the English letters (uppercase and lowercase), keeping non-English letters in their original positions.

Rules:

1. All non-English letters remain in the same position.
2. Reverse the order of English letters only.

Examples:

• Input: "ab-cd"
  Output: "dc-ba"
• Input: "a-bC-dEf-ghIj"
  Output: "j-Ih-gfE-dCba"
• Input: "Test1ng-Leet=code-Q!"
  Output: "Qedo1ct-eeLg=ntse-T!"

Constraints:

• $1 \leq s.length \leq 100$
• ASCII values of characters in s are in the range $[33, 122]$.
• s does not contain '\"' or '\\'.

---

Solution Approach

To solve this problem, follow these steps:

1. Identify English Letters

The key is to focus only on English letters (a-z and A-Z) and ignore all other characters.

2. Reverse Only Letters

Use a two-pointer approach to efficiently reverse the letters:

• Place one pointer at the start and another at the end of the string.
• Swap letters when both pointers point to English letters.
• Skip over non-English letters by advancing or retreating the pointers.

3. Rebuild the String

Keep all non-English characters in their original positions while reversing only the letters.

---

Implementation in Kotlin

fun reverseOnlyLetters(s: String): String {
    val chars = s.toCharArray()
    var left = 0
    var right = s.length - 1

    while (left < right) {
        // Skip non-letters at the left
        while (left < right && !chars[left].isLetter()) {
            left++
        }
        // Skip non-letters at the right
        while (left < right && !chars[right].isLetter()) {
            right--
        }
        // Swap letters
        val temp = chars[left]
        chars[left] = chars[right]
        chars[right] = temp

        left++
        right--
    }

    return String(chars)
}

---

Explanation

1. Convert String to Array: Convert the input string s to a CharArray so we can modify it in place.
2. Two-Pointer Technique:
   • Start two pointers: left at the beginning and right at the end of the array.
   • Use isLetter() to check if the characters are English letters.
   • If both characters are letters, swap them.
   • Otherwise, move the pointers inward while skipping non-letter characters.
3. Return the Result: Convert the modified CharArray back to a string and return it.

---

Dry Run Example

Input: "a-bC-dEf-ghIj"

Step	Array State	Left	Right	Action
Init	['a', '-', 'b', 'C', '-', 'd', 'E', 'f', '-', 'g', 'h', 'I', 'j']	0	12	Start pointers
1	['j', '-', 'b', 'C', '-', 'd', 'E', 'f', '-', 'g', 'h', 'I', 'a']	1	11	Swap 'a' and 'j'
2	['j', '-', 'I', 'C', '-', 'd', 'E', 'f', '-', 'g', 'h', 'b', 'a']	3	10	Swap 'b' and 'I'
3	['j', '-', 'I', 'h', '-', 'd', 'E', 'f', '-', 'g', 'C', 'b', 'a']	4	9	Swap 'C' and 'h'
4	['j', '-', 'I', 'h', '-', 'g', 'E', 'f', '-', 'd', 'C', 'b', 'a']	5	8	Swap 'd' and 'g'
Done	['j', '-', 'I', 'h', '-', 'g', 'f', 'E', '-', 'd', 'C', 'b', 'a']	—	—	Result achieved

Output: "j-Ih-gfE-dCba"

---

Complexity Analysis

1. Time Complexity: $O(n)$, where $n$ is the length of the string. Each character is processed at most once.
2. Space Complexity: $O(n)$ due to the CharArray used for in-place modifications.

---

Why This Approach?

This solution is efficient and easy to understand. By using the two-pointer technique, we minimize unnecessary operations and handle non-letter characters seamlessly.

---

Here are a few different ways to solve the problem, each with varying techniques:

---

1. Using Stack (Explicit Data Structure)

fun reverseOnlyLettersUsingStack(s: String): String {
    val stack = ArrayDeque<Char>()
    for (ch in s) {
        if (ch.isLetter()) stack.push(ch)
    }
    val result = StringBuilder()
    for (ch in s) {
        result.append(if (ch.isLetter()) stack.pop() else ch)
    }
    return result.toString()
}

---

2. Using Regular Expressions (Regex)

fun reverseOnlyLettersUsingRegex(s: String): String {
    val letters = s.filter { it.isLetter() }.reversed()
    var index = 0
    return buildString {
        for (ch in s) {
            append(if (ch.isLetter()) letters[index++] else ch)
        }
    }
}

---

3. Using Mutable List and Two-Pointer Swap

fun reverseOnlyLettersUsingMutableList(s: String): String {
    val chars = s.toMutableList()
    var left = 0
    var right = chars.size - 1

    while (left < right) {
        if (!chars[left].isLetter()) {
            left++
        } else if (!chars[right].isLetter()) {
            right--
        } else {
            chars[left] = chars[right].also { chars[right] = chars[left] }
            left++
            right--
        }
    }
    return chars.joinToString("")
}

---

4. Using Recursion

fun reverseOnlyLettersRecursive(s: String): String {
    val chars = s.toCharArray()
    fun helper(left: Int, right: Int): String {
        if (left >= right) return String(chars)
        if (!chars[left].isLetter()) return helper(left + 1, right)
        if (!chars[right].isLetter()) return helper(left, right - 1)
        chars[left] = chars[right].also { chars[right] = chars[left] }
        return helper(left + 1, right - 1)
    }
    return helper(0, chars.size - 1)
}

---

5. Using Streams (Kotlin Functional Approach)

fun reverseOnlyLettersUsingStream(s: String): String {
    val letters = s.filter { it.isLetter() }.reversed().iterator()
    return s.map { if (it.isLetter()) letters.next() else it }.joinToString("")
}

---

These solutions showcase a variety of approaches—some use explicit data structures like stacks, while others use functional programming or regular expressions. Choose the method that best fits your style or problem constraints!

Summary

The "Reverse Only Letters" problem is a great exercise in string manipulation and working with constraints. Using the two-pointer technique ensures an optimal and clear solution. Whether you’re preparing for coding interviews or improving your problem-solving skills, this approach is worth mastering.

Feel free to try this code on your own and tweak it for other scenarios!