Problem Description

You are given a string s that may contain both uppercase and lowercase letters. Your task is to convert all uppercase letters in the string to their corresponding lowercase letters while keeping all other characters unchanged.

For example:

• If s = "Hello", the output should be "hello"
• If s = "here", the output should be "here" (already lowercase)
• If s = "LOVELY", the output should be "lovely"

The solution uses a bit manipulation technique. It iterates through each character in the string and checks if it's uppercase using c.isupper(). If the character is uppercase, it converts it to lowercase by performing a bitwise OR operation: chr(ord(c) | 32). This works because in ASCII encoding, the difference between an uppercase letter and its lowercase counterpart is exactly 32 (or 0x20 in hexadecimal). By setting the 6th bit (value 32) using the OR operation, we effectively convert uppercase to lowercase. If the character is already lowercase or not a letter, it remains unchanged.

The expression ord(c) | 32 takes the ASCII value of the character and performs a bitwise OR with 32, which sets the 6th bit to 1, converting uppercase letters to lowercase. The result is then converted back to a character using chr(). All processed characters are collected in a list comprehension and joined together to form the final string.

Intuition

When we need to convert uppercase letters to lowercase, the most straightforward approach would be to use built-in string methods like lower(). However, to understand the underlying mechanism, we can look at how characters are represented in ASCII.

In ASCII encoding, uppercase letters ('A' to 'Z') have values from 65 to 90, while lowercase letters ('a' to 'z') have values from 97 to 122. If we examine the difference between any uppercase letter and its lowercase counterpart, we find it's always 32. For instance, 'A' is 65 and 'a' is 97, with a difference of 32.

Looking at this difference in binary reveals an interesting pattern:

• 'A' (65) in binary: 01000001
• 'a' (97) in binary: 01100001

The only difference is the 6th bit (counting from the right, starting at 0). For uppercase letters, this bit is 0, and for lowercase letters, it's 1. The value of the 6th bit position is exactly 32 (2^5).

This observation leads us to a clever bit manipulation trick: to convert any uppercase letter to lowercase, we simply need to set its 6th bit to 1. We can achieve this using the bitwise OR operation with 32. The operation ord(c) | 32 will:

• Set the 6th bit to 1 if it's currently 0 (converting uppercase to lowercase)
• Keep the 6th bit as 1 if it's already 1 (lowercase remains lowercase)

This approach elegantly handles the conversion without needing conditional logic for the actual transformation, though we still check c.isupper() to avoid modifying non-alphabetic characters that might have unexpected results when OR'd with 32.

Solution Approach

The solution implements a single-line approach using list comprehension combined with bit manipulation:

return "".join([chr(ord(c) | 32) if c.isupper() else c for c in s])

Let's break down the implementation step by step:

1. Iterate through each character: We use a list comprehension to process each character c in the string s.

2. Check if character is uppercase: For each character, we use c.isupper() to determine if it's an uppercase letter. This check ensures we only modify uppercase letters and leave everything else (lowercase letters, digits, special characters, spaces) unchanged.

3. Apply bit manipulation for uppercase letters:

   • If the character is uppercase, we convert it using chr(ord(c) | 32)
   • ord(c) gets the ASCII value of the character
   • | 32 performs a bitwise OR operation with 32 (binary: 100000), which sets the 6th bit to 1
   • chr() converts the resulting ASCII value back to a character

4. Keep other characters unchanged: If the character is not uppercase (already lowercase, digit, or special character), we keep it as is.

5. Join the results: The list comprehension produces a list of processed characters, which we join together using "".join() to create the final string.

Example walkthrough with s = "Hello World!":

• 'H' (72) → uppercase → 72 | 32 = 104 → 'h'
• 'e' (101) → not uppercase → remains 'e'
• 'l' (108) → not uppercase → remains 'l'
• 'l' (108) → not uppercase → remains 'l'
• 'o' (111) → not uppercase → remains 'o'
• ' ' (32) → not uppercase → remains ' '
• 'W' (87) → uppercase → 87 | 32 = 119 → 'w'
• And so on...

The time complexity is O(n) where n is the length of the string, as we process each character once. The space complexity is also O(n) for storing the result string.

Example Walkthrough

Let's walk through the solution with s = "HeLLo":

Step 1: Process 'H' (index 0)

• Check: 'H'.isupper() → True (it's uppercase)
• Convert: ord('H') = 72
• Binary of 72: 01001000
• Apply 72 | 32:

  01001000 (72)
  00100000 (32)
  --------
  01101000 (104) = 'h'

• Result: 'H' → 'h'

Step 2: Process 'e' (index 1)

• Check: 'e'.isupper() → False (already lowercase)
• Keep unchanged: 'e'

Step 3: Process 'L' (index 2)

• Check: 'L'.isupper() → True (it's uppercase)
• Convert: ord('L') = 76
• Apply 76 | 32:

  01001100 (76)
  00100000 (32)
  --------
  01101100 (108) = 'l'

• Result: 'L' → 'l'

Step 4: Process 'L' (index 3)

• Check: 'L'.isupper() → True (it's uppercase)
• Convert: ord('L') = 76
• Apply 76 | 32 = 108 = 'l'
• Result: 'L' → 'l'

Step 5: Process 'o' (index 4)

• Check: 'o'.isupper() → False (already lowercase)
• Keep unchanged: 'o'

Final Step: Join all characters

• List of processed characters: ['h', 'e', 'l', 'l', 'o']
• Join with "".join(): "hello"

Output: "hello"

The key insight is that the bitwise OR with 32 always sets the 6th bit to 1, which in ASCII encoding guarantees the character becomes lowercase if it was uppercase, while already lowercase letters remain unchanged.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n is the length of the input string s. The algorithm iterates through each character in the string exactly once. For each character, it performs constant time operations: ord(), isupper(), bitwise OR operation, and chr(). The join() operation also takes O(n) time to concatenate all characters.

Space Complexity: O(n) where n is the length of the input string. The list comprehension creates a new list containing n characters before joining them into the result string. Additionally, the final string created by join() also requires O(n) space. Therefore, the total auxiliary space used is O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Assuming All Characters are Letters

A common mistake is applying the bitwise OR operation to all characters without checking if they're uppercase letters first. This can corrupt non-letter characters.

Incorrect approach:

# WRONG: This corrupts non-letter characters
return "".join([chr(ord(c) | 32) for c in s])

For example, if the input contains digits or special characters:

• '1' (ASCII 49) → 49 | 32 = 49 (happens to stay '1', but by luck)
• '@' (ASCII 64) → 64 | 32 = 96 → '`' (corrupted!)
• '[' (ASCII 91) → 91 | 32 = 123 → '{' (corrupted!)

Solution: Always check c.isupper() before applying the bit manipulation.

2. Incorrect Bit Manipulation for Non-ASCII Characters

The bitwise OR with 32 only works correctly for ASCII uppercase letters (A-Z). For Unicode characters or extended ASCII, this approach may fail.

Problem example:

s = "CAFÉ"  # É is a non-ASCII character
# The bit manipulation won't correctly convert É to é

Solution: Use Python's built-in lower() method for better Unicode support:

return s.lower()  # Handles all Unicode characters correctly

3. Using XOR Instead of OR

Some might mistakenly use XOR (^) thinking it "toggles" the case, but this creates issues.

Incorrect approach:

# WRONG: XOR doesn't guarantee lowercase conversion
chr(ord(c) ^ 32)  # This toggles between upper and lower

This would convert:

• 'A' → 'a' (correct)
• 'a' → 'A' (incorrect - converts lowercase to uppercase!)

Solution: Use OR (|) to set the bit, not XOR to toggle it.

4. Not Handling Empty Strings or None

The code might fail if the input is None or has unexpected types.

Solution: Add input validation:

if not s:
    return s  # Return empty string or None as-is

5. Memory Inefficiency with Large Strings

Creating intermediate lists for very large strings can be memory-intensive.

Alternative approach for better memory usage:

# Using generator expression instead of list comprehension
return "".join(chr(ord(c) | 32) if c.isupper() else c for c in s)

This avoids creating an intermediate list, processing characters on-the-fly.