Scale Engineer

To Lower Case

Easy
#0663Time: 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.1 company
Data structures
String
Companies
Infosys

Prompt

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 <= 100
  • s consists 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 c of the input string s.
  • Check if c is 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 c to result.
  • In Java, appending to a string in a loop (result += ...) creates a new string object in each iteration.
  • Return the result string 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.

Solutions

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 ); } }

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.

← Previous

Previous problem

Next →

Next problem