LeetCode 3823 - Reverse Letters Then Special Characters in a String

This problem gives us a string s that contains two types of characters: 1. Lowercase English letters ('a' to 'z') 2. Special characters from the set "!@$%^&()" We must perform two independent reversals, in a specific order.

leetcodeeasytwo-pointersstringsimulation

LeetCode Problem 3823

Difficulty: 🟢 Easy
Topics: Two Pointers, String, Simulation

Solution

LeetCode 3823 - Reverse Letters Then Special Characters in a String

Problem Understanding

This problem gives us a string s that contains two types of characters:

  1. Lowercase English letters ('a' to 'z')
  2. Special characters from the set "!@#$%^&*()"

We must perform two independent reversals, in a specific order.

First, we extract all lowercase letters from the string while preserving their relative order. We reverse this sequence of letters and place the reversed letters back into the positions that originally contained letters.

After that, we do the same for special characters. We extract all special characters, reverse their order, and place them back into the positions that originally contained special characters.

An important observation is that letter positions always remain letter positions, and special character positions always remain special character positions. We never move a letter into a special character position or vice versa.

For example, consider:

)ebc#da@f(

The letter positions contain:

e b c d a f

Reversing them gives:

f a d c b e

After placing them back:

)fad#cb@e(

The special characters are:

) # @ (

Reversing them gives:

( @ # )

Placing them back into the special character positions produces:

(fad@cb#e)

The constraints are very small:

1 <= s.length <= 100

This means almost any reasonable solution will be fast enough. However, we should still aim for a clean linear-time approach.

Some important edge cases include strings containing only letters, strings containing only special characters, strings of length one, and strings where one category appears exactly once. In all of these situations, reversing a sequence of length 0 or 1 should leave it unchanged.

Approaches

Brute Force Approach

A straightforward solution is to repeatedly scan the string looking for the next available reversed character whenever we encounter a letter or special character position.

For every position, we could search backward through the original string to find the appropriate replacement character of the same type. While this works, it performs many repeated scans.

Since each position may trigger another traversal of the string, the overall complexity can become quadratic.

The approach is correct because it explicitly finds the character that should occupy each position after reversal, but it performs unnecessary repeated work.

Optimal Approach

The key observation is that letters and special characters are completely independent groups.

We can:

  1. Collect all letters into one array.
  2. Collect all special characters into another array.
  3. Reverse both arrays.
  4. Build the answer by traversing the original string once.
  • If the current position originally held a letter, take the next reversed letter.
  • Otherwise, take the next reversed special character.

This works because every letter position must receive characters from the reversed letter sequence, and every special position must receive characters from the reversed special sequence.

By preprocessing both groups once and reconstructing the string in a single pass, we avoid repeated scanning.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(n) Repeatedly searches for matching reversed characters
Optimal O(n) O(n) Extract, reverse, and reconstruct in linear time

Algorithm Walkthrough

  1. Create an empty list called letters.
  2. Create an empty list called specials.
  3. Traverse the string once.
  • If the current character is a lowercase letter, append it to letters.
  • Otherwise, append it to specials.
  1. Reverse both lists.
  • letters.reverse()
  • specials.reverse()
  1. Create two indices:
  • letter_index = 0
  • special_index = 0
  1. Create an empty result list.
  2. Traverse the original string again.

  • If the current character is a lowercase letter:

  • Append letters[letter_index] to the result.

  • Increment letter_index.

  • Otherwise:

  • Append specials[special_index] to the result.

  • Increment special_index.

  1. Join the result list into a string and return it.

Why it works

The algorithm separates the string into two independent categories. Every letter position receives characters from the reversed letter sequence, and every special character position receives characters from the reversed special sequence. Since each reversed sequence is consumed exactly once in order, the resulting string is precisely what the problem requires.

Python Solution

class Solution:
    def reverseByType(self, s: str) -> str:
        letters = []
        specials = []

        for ch in s:
            if 'a' <= ch <= 'z':
                letters.append(ch)
            else:
                specials.append(ch)

        letters.reverse()
        specials.reverse()

        letter_index = 0
        special_index = 0
        result = []

        for ch in s:
            if 'a' <= ch <= 'z':
                result.append(letters[letter_index])
                letter_index += 1
            else:
                result.append(specials[special_index])
                special_index += 1

        return ''.join(result)

The implementation begins by collecting letters and special characters into separate arrays. This preserves their original ordering inside each category.

Next, both arrays are reversed. At this point, letters contains exactly the sequence that should fill letter positions, and specials contains exactly the sequence that should fill special character positions.

The second traversal reconstructs the answer. Whenever a letter position is encountered, the next reversed letter is used. Whenever a special position is encountered, the next reversed special character is used.

Finally, the accumulated characters are joined into the final string.

Go Solution

func reverseByType(s string) string {
	letters := make([]byte, 0)
	specials := make([]byte, 0)

	for i := 0; i < len(s); i++ {
		ch := s[i]

		if ch >= 'a' && ch <= 'z' {
			letters = append(letters, ch)
		} else {
			specials = append(specials, ch)
		}
	}

	for left, right := 0, len(letters)-1; left < right; left, right = left+1, right-1 {
		letters[left], letters[right] = letters[right], letters[left]
	}

	for left, right := 0, len(specials)-1; left < right; left, right = left+1, right-1 {
		specials[left], specials[right] = specials[right], specials[left]
	}

	letterIndex := 0
	specialIndex := 0
	result := make([]byte, len(s))

	for i := 0; i < len(s); i++ {
		ch := s[i]

		if ch >= 'a' && ch <= 'z' {
			result[i] = letters[letterIndex]
			letterIndex++
		} else {
			result[i] = specials[specialIndex]
			specialIndex++
		}
	}

	return string(result)
}

The Go solution follows exactly the same logic as the Python version. Since strings are immutable in Go, a byte slice is used to build the result efficiently. Reversal is performed manually using the standard two-pointer swapping technique.

Because the input contains only ASCII characters, indexing by byte is completely safe.

Worked Examples

Example 1

Input

)ebc#da@f(

Step 1: Collect characters

Character Type
) Special
e Letter
b Letter
c Letter
# Special
d Letter
a Letter
@ Special
f Letter
( Special

Letters:

[e, b, c, d, a, f]

Specials:

[), #, @, (]

Step 2: Reverse both lists

Letters:

[f, a, d, c, b, e]

Specials:

[(, @, #, )]

Step 3: Reconstruct

Position Original Output Character
0 ) (
1 e f
2 b a
3 c d
4 # @
5 d c
6 a b
7 @ #
8 f e
9 ( )

Result:

(fad@cb#e)

Example 2

Input

z

Collected:

letters = [z]
specials = []

After reversal:

letters = [z]
specials = []

Reconstruction:

z

Output:

z

Example 3

Input

!@#$%^&*()

Collected:

letters = []
specials = [!, @, #, $, %, ^, &, *, (, )]

After reversal:

specials = [), (, *, &, ^, %, $, #, @, !]

Reconstruction produces:

)(*&^%$#@!

Complexity Analysis

Measure Complexity Explanation
Time O(n) One pass to collect characters, one pass to reconstruct
Space O(n) Stores letters, special characters, and result

The string is traversed a constant number of times. Every character is processed only a few times, so the running time grows linearly with the input length. Additional storage proportional to the input size is required for the extracted groups and the final result.

Test Cases

sol = Solution()

assert sol.reverseByType(")ebc#da@f(") == "(fad@cb#e)"  # provided example
assert sol.reverseByType("z") == "z"  # single letter
assert sol.reverseByType("!@#$%^&*()") == ")(*&^%$#@!"  # only special characters

assert sol.reverseByType("abc") == "cba"  # only letters
assert sol.reverseByType("!") == "!"  # single special character

assert sol.reverseByType("a!b") == "b!a"  # one special in middle
assert sol.reverseByType("!a@") == "@a!"  # one letter only

assert sol.reverseByType("ab#cd") == "dc#ba"  # special remains in special position
assert sol.reverseByType("#ab$cd%") == "%dc$ba#"  # multiple special positions

assert sol.reverseByType("a#") == "a#"  # one letter and one special
assert sol.reverseByType("#a") == "#a"  # reversed groups of size one

assert sol.reverseByType("a!b@c#d") == "d#c@b!a"  # alternating pattern
assert sol.reverseByType("abcd!!!!") == "dcba!!!!"  # special sequence unchanged after reverse

Test Case Summary

Test Why
")ebc#da@f(" Official mixed example
"z" Single letter
"!@#$%^&*()" No letters present
"abc" Letters only
"!" Single special character
"a!b" One special in middle
"!a@" One letter only
"ab#cd" Mixed categories
"#ab$cd%" Multiple special positions
"a#" Minimum mixed case
"#a" Reverse ordering of categories
"a!b@c#d" Alternating pattern
"abcd!!!!" Large block of specials

Edge Cases

String Contains Only Letters

A common mistake is to assume that both character categories exist. For an input like "abcdef", the special character list is empty. The algorithm handles this naturally because the special list is never accessed during reconstruction. The final result becomes "fedcba".

String Contains Only Special Characters

For an input like "!@#$", the letter list is empty. A buggy implementation might try to access letter indices that do not exist. In this solution, reconstruction only consumes from the special list because every position is a special character position.

Only One Character of a Category

Consider "!a@". There is only one letter. Reversing a sequence of length one should not change it. The algorithm reverses the letter list, but the result remains identical. This guarantees correct behavior for all groups of size zero or one.

Alternating Character Types

Inputs such as "a!b@c#d" can expose bugs where positions are not preserved correctly. The algorithm always checks the original character type at each position and pulls from the matching reversed sequence. As a result, every letter remains in a letter position and every special character remains in a special character position.

Minimum Length Input

The smallest possible input length is 1. Whether the input is "a" or "!", the extracted group contains a single element and reconstruction simply returns the same character. The implementation therefore handles the minimum constraint without any special-case code.