Jobs

Interviews

Discussions

To Lower Case

Easy

Google

2 views

Topics:

Strings

Given a string s, return the string after replacing every uppercase letter with the same lowercase letter.

For example:

If s = "Hello", the output should be "hello".
If s = "here", the output should be "here".
If s = "LOVELY", the output should be "lovely".

Can you provide an efficient algorithm to achieve this? What is the time and space complexity of your solution? Are there any edge cases to consider?

To Lower Case

Easy

Google

2 views

Topics:

Strings

Given a string s, return the string after replacing every uppercase letter with the same lowercase letter.

For example:

If s = "Hello", the output should be "hello".
If s = "here", the output should be "here".
If s = "LOVELY", the output should be "lovely".

Can you provide an efficient algorithm to achieve this? What is the time and space complexity of your solution? Are there any edge cases to consider?

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Will the input string contain only ASCII characters, or should I consider Unicode characters as well?
Is the input string guaranteed to be non-null?
Can the input string be empty?
Should I modify the string in-place, or return a new lowercase string?
What should I return if the input is null?

Brute Force Solution

Approach

To convert a string to lowercase using brute force, we examine each letter individually. If a letter is uppercase, we change it to its lowercase equivalent; otherwise, we leave it as is.

Here's how the algorithm would work step-by-step:

Look at the first letter of the string.
Check if this letter is an uppercase letter (A, B, C, and so on).
If it is, find the corresponding lowercase letter (a, b, c, and so on) and replace the uppercase letter with it.
If it isn't an uppercase letter, leave it alone.
Move on to the next letter in the string and repeat the same process.
Continue this process for every letter in the string, one after the other.
Once you've checked and potentially changed every letter, the string will be entirely in lowercase.

Code Implementation

def to_lower_case_brute_force(input_string):
    string_as_list = list(input_string)

    for character_index in range(len(string_as_list)):
        character = string_as_list[character_index]

        # Check if the character is an uppercase letter
        if 'A' <= character <= 'Z':

            # Calculate the offset from 'A' to convert to lowercase
            uppercase_offset = ord(character) - ord('A')
            lowercase_character = chr(ord('a') + uppercase_offset)

            # Replace the uppercase letter with its lowercase equivalent

            string_as_list[character_index] = lowercase_character

    return "".join(string_as_list)

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through each character of the input string once. For each character, it performs a constant-time check to determine if it's an uppercase letter and a constant-time conversion if needed. Therefore, the time complexity is directly proportional to the length of the string, denoted as n, resulting in O(n) time complexity.

Space Complexity

O(1) – The provided algorithm iterates through the input string, potentially modifying characters in place. It doesn't explicitly mention creating any auxiliary data structures like arrays, lists, or hash maps to store intermediate results. Therefore, the space complexity is constant, as it only requires a fixed amount of extra memory regardless of the input string's length (N). No additional space is used beyond the input string itself, leading to O(1) space complexity.

Optimal Solution

Approach

We want to change uppercase letters to lowercase. We can achieve this by looking at each letter and, if it's uppercase, changing it based on its position in the alphabet.

Here's how the algorithm would work step-by-step:

Look at each letter in the given text one by one.
If a letter is uppercase (A, B, C, etc.), figure out its position in the alphabet.
Add a specific number to that position to shift it to the corresponding lowercase letter (a, b, c, etc.).
Change the uppercase letter to the new lowercase letter you calculated.
If the letter isn't uppercase, leave it as it is.
Combine all the letters together to form the final lowercase text.

Code Implementation

def to_lower_case(input_string):
    result_string = ''
    for char in input_string:
        # Check if the character is an uppercase letter
        if 'A' <= char <= 'Z':
            # Calculate the ASCII value of the lowercase equivalent.
            lowercase_char = chr(ord(char) + 32)
            result_string += lowercase_char

        # If not uppercase, append the original character
        else:
            result_string += char
    return result_string

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through each character of the input string of length n. For each character, it performs a constant-time check to determine if it's an uppercase letter. If it is, a constant-time conversion is performed. Therefore, the time complexity is directly proportional to the length of the input string. Thus the algorithm has a time complexity of O(n).

Space Complexity

O(N) – The provided algorithm transforms the input string by iterating through each character. While it doesn't explicitly mention creating a new string, the implied operation of combining the potentially modified characters suggests the creation of a new string of the same length as the input. Thus, an auxiliary space of size N is required to store this new lower-cased string, where N is the length of the input string. Therefore the space complexity is O(N).

Edge Cases

Case	How to Handle
Null or empty input string	Return an empty string or null depending on the language convention for empty inputs.
String containing only non-alphabetic characters	The algorithm should correctly skip these characters, leaving them unchanged in the output string.
String with mixed-case alphabets and non-alphabets	Only upper-case alphabets should be converted and other characters should remain as is.
String with special characters (e.g., unicode)	Handle unicode characters correctly based on the language's unicode support and conversion functions.
String with numbers as input	Numbers should be kept as is since toLower() is only for upper case letters.
Maximum string length (memory constraints)	Ensure the solution avoids memory overflow issues when dealing with very large strings by allocating only the necessary memory.
Input contains all uppercase characters	The entire input will be converted to lowercase as expected.
Input contains all lowercase characters	The entire input will remain the same since no changes need to be made.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Will the input string contain only ASCII characters, or should I consider Unicode characters as well?
Is the input string guaranteed to be non-null?
Can the input string be empty?
Should I modify the string in-place, or return a new lowercase string?
What should I return if the input is null?

Brute Force Solution

Approach

To convert a string to lowercase using brute force, we examine each letter individually. If a letter is uppercase, we change it to its lowercase equivalent; otherwise, we leave it as is.

Here's how the algorithm would work step-by-step:

Look at the first letter of the string.
Check if this letter is an uppercase letter (A, B, C, and so on).
If it is, find the corresponding lowercase letter (a, b, c, and so on) and replace the uppercase letter with it.
If it isn't an uppercase letter, leave it alone.
Move on to the next letter in the string and repeat the same process.
Continue this process for every letter in the string, one after the other.
Once you've checked and potentially changed every letter, the string will be entirely in lowercase.

Code Implementation

def to_lower_case_brute_force(input_string):
    string_as_list = list(input_string)

    for character_index in range(len(string_as_list)):
        character = string_as_list[character_index]

        # Check if the character is an uppercase letter
        if 'A' <= character <= 'Z':

            # Calculate the offset from 'A' to convert to lowercase
            uppercase_offset = ord(character) - ord('A')
            lowercase_character = chr(ord('a') + uppercase_offset)

            # Replace the uppercase letter with its lowercase equivalent

            string_as_list[character_index] = lowercase_character

    return "".join(string_as_list)

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

We want to change uppercase letters to lowercase. We can achieve this by looking at each letter and, if it's uppercase, changing it based on its position in the alphabet.

Here's how the algorithm would work step-by-step:

Look at each letter in the given text one by one.
If a letter is uppercase (A, B, C, etc.), figure out its position in the alphabet.
Add a specific number to that position to shift it to the corresponding lowercase letter (a, b, c, etc.).
Change the uppercase letter to the new lowercase letter you calculated.
If the letter isn't uppercase, leave it as it is.
Combine all the letters together to form the final lowercase text.

Code Implementation

def to_lower_case(input_string):
    result_string = ''
    for char in input_string:
        # Check if the character is an uppercase letter
        if 'A' <= char <= 'Z':
            # Calculate the ASCII value of the lowercase equivalent.
            lowercase_char = chr(ord(char) + 32)
            result_string += lowercase_char

        # If not uppercase, append the original character
        else:
            result_string += char
    return result_string

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input string	Return an empty string or null depending on the language convention for empty inputs.
String containing only non-alphabetic characters	The algorithm should correctly skip these characters, leaving them unchanged in the output string.
String with mixed-case alphabets and non-alphabets	Only upper-case alphabets should be converted and other characters should remain as is.
String with special characters (e.g., unicode)	Handle unicode characters correctly based on the language's unicode support and conversion functions.
String with numbers as input	Numbers should be kept as is since toLower() is only for upper case letters.
Maximum string length (memory constraints)	Ensure the solution avoids memory overflow issues when dealing with very large strings by allocating only the necessary memory.
Input contains all uppercase characters	The entire input will be converted to lowercase as expected.
Input contains all lowercase characters	The entire input will remain the same since no changes need to be made.