709. To Lower Case

EasyString
Leetcode Link

Problem Description

The problem requires us to take an input string s and return a new string where all uppercase letters have been converted to their corresponding lowercase counterparts. The task focuses on modifying the letter cases without altering any other characters in the string. For instance, if the input string is "LeetCode", the output should be "leetcode".

Intuition

To solve this problem, we need to iterate over each character in the string s and check if it's an uppercase letter. If it is, we convert it to lowercase. The solution uses a list comprehension to create a new list of characters, where each uppercase character is converted by using the bitwise OR operator with 32. This works because, in the ASCII character encoding, adding 32 to the ASCII value of an uppercase letter gives us the ASCII value of the corresponding lowercase letter. The chr(ord(c) | 32) expression inside the list comprehension checks if a character c is uppercase using the isupper() method, and if it is, applies the | 32 operation which adds 32 to the character's ASCII value, effectively converting it to lowercase.

This approach is efficient because:

  1. It avoids branching logic like if-else statements within the list comprehension, which can be slower in Python.
  2. The bitwise operation is an efficient way to convert characters from uppercase to lowercase.
  3. The use of a list comprehension allows for the creation of the new lowercased string in a single line of code.

The final string is obtained by joining all characters in the resultant list with an empty string separator "".

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What data structure does Breadth-first search typically uses to store intermediate states?

Solution Approach

The implementation uses a straightforward and efficient algorithm to convert uppercase letters to lowercase. The process involves the following steps:

  1. Iterate over each character in the input string s using a list comprehension.
  2. For each character c, check if it is an uppercase letter by calling the isupper() method.
  3. If c is uppercase, apply the bitwise OR operation | with 32 to the ASCII value of c to get the ASCII value of the lowercase equivalent. This is done by first using ord(c) to get the ASCII value of c, then applying the bitwise operation, and finally converting back to a character with chr().
  4. If c is not uppercase, it is left unchanged.
  5. The list comprehension creates a list of characters, with uppercase characters now converted to lowercase.
  6. The final lowercase string is produced by concatenating all characters in the list using the join method with an empty string "" as the separator.

No additional data structures are required aside from the list created by the list comprehension and the final string returned.

This pattern is based on the property of ASCII values for letters:

  • The ASCII values of uppercase and lowercase letters have a specific numerical relationship: the difference between the ASCII values of an uppercase letter and its corresponding lowercase letter is exactly 32.
  • The bitwise OR operation with 32 effectively adds 32 to the ASCII value if the number is within the range of uppercase letters in ASCII (since their binary representations are such that the value 32 would only change the bit corresponding to the lowercase bit).

Here is the core line of code that performs the conversion:

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

This line is Pythonic and leverages the features of the language for a concise and efficient implementation.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What is the worst case running time for finding an element in a binary search tree(not necessarily balanced) of size n?

Example Walkthrough

Let's illustrate the solution approach with a simple example.

Suppose our input string s is "Python3.8". We aim to convert any uppercase letters to lowercase while leaving other characters unchanged. To make it easier to follow, let's walk through the process step by step for this input:

  1. The string "Python3.8" is composed of characters: 'P', 'y', 't', 'h', 'o', 'n', '3', '.', and '8'.
  2. We start iterating over each character, starting with 'P'.
  3. 'P' is an uppercase letter, so we check its ASCII value. The ASCII value for 'P' is 80.
  4. We then apply the bitwise OR operation (|) with 32, which is 80 | 32. The binary representation of 80 is 1010000, and the binary representation of 32 is 0100000. The OR operation yields 1110000, which is the binary representation of 112 - the ASCII value of 'p'.
  5. We convert the ASCII value back to a character with chr(), resulting in 'p'.
  6. We continue the process with 'y', which isn't an uppercase letter, so it remains unchanged.
  7. We proceed with the rest of the characters, and since there are no more uppercase letters, they all remain unchanged.
  8. After processing all characters, we obtain a list of characters: ['p', 'y', 't', 'h', 'o', 'n', '3', '.', '8'].
  9. We join all characters in the list to produce the final string, using "".join([...]).
  10. The final output is "python3.8".

The core line of Python code that performs this operation looks like this:

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

For our example "Python3.8", this line of code will return "python3.8", as expected, with the uppercase 'P' converted to a lowercase 'p'.

Solution Implementation

1class Solution:
2    def toLowerCase(self, string: str) -> str:
3        # Create a lowercase version of the given string
4        # by iterating over each character in the string
5        lowercase_string = "".join([
6            # Convert uppercase letters to lowercase by using bitwise OR with 32 
7            # which effectively adds 32 to ASCII value of uppercase letters to get 
8            # their lowercase counterparts because in ASCII table, the difference 
9            # between uppercase and lowercase letters is 32
10            chr(ord(char) | 32) if 'A' <= char <= 'Z' else char 
11            for char in string
12        ])
13        return lowercase_string
14
1class Solution {
2  
3    // Method to convert all uppercase letters in a string to lowercase
4    public String toLowerCase(String str) {
5        // Convert the input string to an array of characters
6        char[] characters = str.toCharArray();
7      
8        // Iterate over each character of the array
9        for (int i = 0; i < characters.length; ++i) {
10            // Check if the current character is an uppercase letter
11            if (characters[i] >= 'A' && characters[i] <= 'Z') {
12                // Perform a bitwise OR operation with 32 to convert
13                // the uppercase letter to a lowercase letter
14                characters[i] |= 32;
15            }
16        }
17      
18        // Return the new string with all characters converted to lowercase
19        return String.valueOf(characters);
20    }
21}
22
1class Solution {
2public:
3    // Function to convert a string to lowercase
4    string toLowerCase(string str) {
5        // Iterate over each character in the string
6        for (char& character : str) {
7            // Check if the character is an uppercase letter
8            if (character >= 'A' && character <= 'Z') {
9                // Convert it to lowercase by adding the difference in ASCII values
10                character |= 32; // Bitwise OR operation with 32 to make the character lowercase
11            }
12        }
13        // Return the modified string
14        return str;
15    }
16};
17
1/**
2 * Converts a string to lowercase.
3 * @param {string} str - The string to be converted to lowercase.
4 * @returns {string} The lowercase equivalent of the input string.
5 */
6function toLowerCase(str: string): string {
7    // Convert the string to an array of characters, then map each character
8    // to its lowercase equivalent by OR-ing the character's char code with 32.
9    // This works because in the ASCII table, the difference between uppercase
10    // and lowercase letters is 32.
11    // Finally, join the array back into a string.
12    const lowerCaseString = [...str].map(char =>
13        // Convert char to lowercase by OR-ing with 32, and then convert back to string
14        String.fromCharCode(char.charCodeAt(0) | 32)
15    ).join('');
16
17    // Return the resulting lowercase string
18    return lowerCaseString;
19}
20
Not Sure What to Study? Take the 2-min Quiz：

Given an array of 1,000,000 integers that is almost sorted, except for 2 pairs of integers. Which algorithm is fastest for sorting the array?

Time and Space Complexity

The given Python code snippet converts each uppercase letter in a string to lowercase by using a bitwise OR operation with the space character, which is 32 in decimal (' ' has an ASCII value of 32). The bit manipulation here relies on the fact that in ASCII, setting the sixth bit of an uppercase letter's ASCII value to 1 will convert it to its lowercase equivalent. Here's how the code breaks down in terms of time and space complexity:

Time Complexity:

  • The function iterates over each character in the string s once.
  • During each iteration, it performs a constant-time check to see if the character is uppercase (c.isupper()) and then applies the bitwise operation (ord(c) | 32) if needed.
  • The overall time complexity is O(n), where n is the length of the input string s. This is because the operations inside the loop are constant time and the loop runs n times, where n is the number of characters in the string.

Space Complexity:

  • The space complexity of the code is also O(n). This is due to the list comprehension creating a new list that stores the resultant characters before joining them into a final string. The size of this list scales linearly with the number of characters in the input string, making the space required proportional to n.

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

Fast Track Your Learning with Our Quick Skills Quiz:

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30
1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

Recommended Readings

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Runtime to Algo Cheat Sheet

Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫