To Lower Case
EasyPrompt
Given a string s, return the string after replacing every uppercase letter with the same lowercase letter.
Example 1:
Input: s = "Hello"
Output: "hello"Example 2:
Input: s = "here"
Output: "here"Example 3:
Input: s = "LOVELY"
Output: "lovely"
Constraints:
1 <= s.length <= 100sconsists of printable ASCII characters.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach manually builds the lowercase string by iterating through the input string and appending characters to a result string one by one. For each character, it checks if it's an uppercase letter and converts it if necessary before appending. While conceptually simple, this method is very inefficient in Java due to the nature of string concatenation.
Algorithm
- Initialize an empty string,
result. - Iterate through each character
cof the input strings. - Check if
cis an uppercase letter (from 'A' to 'Z'). - If it is, convert it to its lowercase equivalent by adding 32 to its ASCII value and append it to
result. - If it's not, append the original character
ctoresult. - In Java, appending to a string in a loop (
result += ...) creates a new string object in each iteration. - Return the
resultstring after the loop.
Walkthrough
We start with an empty string result. We then loop through the input string s from the first to the last character. In each step, we examine the current character. If it falls within the ASCII range of uppercase English letters ('A' through 'Z'), we convert it to lowercase. The conversion is done by adding a fixed offset ('a' - 'A', which is 32) to the character's ASCII value. This new lowercase character is then appended to our result string. If the character is not an uppercase letter, we append it unchanged. The main drawback is that in Java, the += operator for strings creates a new string and copies the content of the old string plus the new character. Doing this repeatedly in a loop leads to O(N^2) time complexity.
class Solution { public String toLowerCase(String s) { String result = ""; for (char c : s.toCharArray()) { if (c >= 'A' && c <= 'Z') { result += (char) (c + 32); } else { result += c; } } return result; }}Complexity
Time
O(N^2) in Java, where N is the length of the string. Each string concatenation takes time proportional to the length of the strings being joined, leading to a quadratic overall time complexity.
Space
O(N^2) in Java. The total memory allocated for all intermediate strings created during concatenation is 1 + 2 + ... + N, which is quadratic.
Trade-offs
Pros
Easy to understand and implement without using advanced data structures.
Demonstrates basic loop and character manipulation logic.
Cons
Extremely inefficient in languages with immutable strings like Java, leading to a quadratic time complexity.
Creates a large number of intermediate string objects, which puts pressure on the garbage collector and consumes excessive memory.
A much more efficient manual approach involves operating on a mutable data structure, like a character array. The input string is first converted to a character array. We then iterate through this array, modifying any uppercase letters to lowercase 'in-place' within the array. Finally, a new string is constructed from this modified array. This avoids the costly creation of intermediate strings.
Algorithm
- Convert the input string
sinto a character array,chars. - Iterate through the
charsarray from the first to the last element. - For each character
cin the array, check if it is an uppercase letter ('A' through 'Z'). - If it is, update the character in the array at the current position with its lowercase equivalent. This is done by adding 32 to its ASCII value:
chars[i] = (char) (chars[i] + 32). - After the loop finishes, create a new string from the modified character array.
- Return the new string.
Walkthrough
This method improves upon the naive string concatenation by avoiding its O(N^2) overhead. First, we call s.toCharArray() to get a character array representation of the string. This operation takes O(N) time and space. Then, we loop through this array. For each character, we check if it's an uppercase letter. If it is, we convert it to lowercase by adding 32 to its ASCII value and update the array at that index. Since we are modifying the array in-place, this loop takes O(N) time. Finally, we construct a new string from the modified character array using new String(chars), which also takes O(N) time. This approach is efficient and demonstrates a good understanding of string immutability and how to work around it.
A similar, and also very common, alternative is to use a StringBuilder which provides an efficient append method and can be converted to a string at the end.
class Solution { public String toLowerCase(String s) { char[] chars = s.toCharArray(); for (int i = 0; i < chars.length; i++) { if (chars[i] >= 'A' && chars[i] <= 'Z') { chars[i] = (char) (chars[i] + 32); } } return new String(chars); }}Complexity
Time
O(N), where N is the length of the string. We perform a single pass over the character array.
Space
O(N), where N is the length of the string. This space is required to store the character array.
Trade-offs
Pros
Efficient with O(N) time complexity.
Avoids the performance pitfalls of string concatenation in a loop.
Demonstrates understanding of string immutability and efficient string manipulation techniques.
Cons
Slightly more verbose than using a built-in function.
Requires manual conversion logic, which could be error-prone if not handled carefully.
The simplest, most readable, and idiomatic solution is to use the built-in toLowerCase() method provided by the String class in Java. This method is highly optimized and handles the conversion internally.
Algorithm
- Call the built-in
toLowerCase()method on the input strings. - Return the result.
Walkthrough
Most programming languages provide standard library functions for common tasks like string case conversion. In Java, the String class has a toLowerCase() method that does exactly what the problem asks for. It iterates through the string, converts any uppercase characters to their lowercase counterparts, and returns a new string with the result. Because strings are immutable in Java, this method does not change the original string but rather returns a new one. This approach is not only the most concise but is also typically the most performant due to low-level optimizations within the Java Virtual Machine (JVM).
class Solution { public String toLowerCase(String s) { return s.toLowerCase(); }}Complexity
Time
O(N), where N is the length of the string. The implementation must scan the entire string to find and convert characters.
Space
O(N), where N is the length of the string. A new string of length N is created to store the result. In the specific case where the input string has no uppercase letters, some JVM implementations may optimize this by returning the original string object, resulting in O(1) space.
Trade-offs
Pros
Extremely simple, concise, and readable.
It's the idiomatic way to solve this problem in a real-world scenario.
Highly performant due to internal JVM optimizations.
Less prone to bugs as the logic is handled by a well-tested library function.
Cons
Abstracts away the underlying implementation, which might not be what an interviewer wants if they are testing fundamental knowledge.
Solutions
Solution
class Solution { public String toLowerCase ( String s ) { char [] cs = s . toCharArray (); for ( int i = 0 ; i < cs . length ; ++ i ) { if ( cs [ i ] >= 'A' && cs [ i ] <= 'Z' ) { cs [ i ] |= 32 ; } } return String . valueOf ( cs ); } }class Solution { public: string toLowerCase ( string s ) { for ( char & c : s ) { if ( c >= 'A' && c <= 'Z' ) { c |= 32 ; } } return s ; } };class Solution : def toLowerCase ( self , s : str ) -> str : return "" . join ([ chr ( ord ( c ) | 32 ) if c . isupper () else c for c in s ])Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.