Jobs

Interviews

Discussions

Reformat The String

Easy

Asked by:

26 views

Topics:

Strings

You are given an alphanumeric string s. (Alphanumeric string is a string consisting of lowercase English letters and digits).

You have to find a permutation of the string where no letter is followed by another letter and no digit is followed by another digit. That is, no two adjacent characters have the same type.

Return the reformatted string or return an empty string if it is impossible to reformat the string.

Example 1:

Input: s = "a0b1c2"
Output: "0a1b2c"
Explanation: No two adjacent characters have the same type in "0a1b2c". "a0b1c2", "0a1b2c", "0c2a1b" are also valid permutations.

Example 2:

Input: s = "leetcode"
Output: ""
Explanation: "leetcode" has only characters so we cannot separate them by digits.

Example 3:

Input: s = "1229857369"
Output: ""
Explanation: "1229857369" has only digits so we cannot separate them by characters.

Constraints:

1 <= s.length <= 500
s consists of only lowercase English letters and/or digits.

Try coding it in LeetCode

Reformat The String

Easy

Asked by:

26 views

Topics:

Strings

You are given an alphanumeric string s. (Alphanumeric string is a string consisting of lowercase English letters and digits).

You have to find a permutation of the string where no letter is followed by another letter and no digit is followed by another digit. That is, no two adjacent characters have the same type.

Return the reformatted string or return an empty string if it is impossible to reformat the string.

Example 1:

Input: s = "a0b1c2"
Output: "0a1b2c"
Explanation: No two adjacent characters have the same type in "0a1b2c". "a0b1c2", "0a1b2c", "0c2a1b" are also valid permutations.

Example 2:

Input: s = "leetcode"
Output: ""
Explanation: "leetcode" has only characters so we cannot separate them by digits.

Example 3:

Input: s = "1229857369"
Output: ""
Explanation: "1229857369" has only digits so we cannot separate them by characters.

Constraints:

1 <= s.length <= 500
s consists of only lowercase English letters and/or digits.

Try coding it in LeetCode

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:

What is the maximum length of the input string `s`?
Can the input string `s` be empty or null?
If it is impossible to reformat the string, should I return an empty string or null?
Does the input string `s` only contain lowercase alphanumeric characters, or can it contain other characters like spaces or special symbols?
If multiple valid reformatted strings exist, is any one of them acceptable?

Brute Force Solution

Approach

The brute force approach to reformatting a string means we'll explore every possible arrangement. We will try to combine letters and digits in every conceivable order to meet the problem's alternating requirement, without any shortcuts or clever tricks.

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

First, count how many letters and how many digits you have.
If the difference between the count of letters and digits is more than one, it is impossible to reformat the string, and you can stop.
If it is possible, consider two options: starting with a letter or starting with a digit.
For each option (starting with a letter or digit), try all possible arrangements where letters and digits alternate.
Check if each arrangement is valid: meaning, does it actually alternate between a letter and a digit?
If an arrangement is valid, save it.
Once you've tried all arrangements for both starting options, see if you've saved any valid arrangements.
If you have saved arrangements, pick any one of them as the result. The problem states any valid answer is okay.

Code Implementation

def reformat_string_brute_force(input_string):
    letters = [char for char in input_string if char.isalpha()]
    digits = [char for char in input_string if char.isdigit()]

    # Check if the string can be reformatted
    if abs(len(letters) - len(digits)) > 1:
        return ""

    from itertools import permutations

    # Try all possible permutations
    for permutation in permutations(letters + digits):
        reformatted_string = "".join(permutation)

        # Verify the reformatting pattern
        valid = True
        for i in range(len(reformatted_string) - 1):
            if reformatted_string[i].isalpha() == reformatted_string[i+1].isalpha():
                valid = False
                break

        if valid:
            return reformatted_string

    return ""

Big(O) Analysis

Time Complexity

O((n!)) – The brute force approach explores all possible arrangements (permutations) of the string. Generating all permutations of a string of length n takes O(n!) time. For each of these n! permutations, we need to validate if the arrangement alternates between digits and letters, which takes O(n) time. However, since the permutation generation dominates the cost, and validation occurs for each permutation, the overall time complexity is driven by the permutation generation. Hence the overall time complexity is O(n!).

Space Complexity

O(N!) – The described brute force approach explores all possible arrangements of the input string. To achieve this, it implicitly uses space to store each generated permutation. In the worst case, where the string contains a nearly equal number of letters and digits, the number of possible arrangements approaches N!, where N is the length of the string. Therefore, storing all possible arrangements in memory, even temporarily, leads to a space complexity of O(N!).

Optimal Solution

Approach

The goal is to rearrange a string containing letters and numbers so that no two adjacent characters are of the same type. We aim to create an alternating sequence as efficiently as possible. This involves counting the occurrences of letters and numbers and strategically building the new string based on these counts.

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

First, count how many letters and how many numbers are in the string.
Determine which type of character (letter or number) appears more frequently.
If the difference in counts between letters and numbers is more than 1, it's impossible to rearrange the string as requested, so indicate that there's no solution.
Otherwise, create a new string by alternating letters and numbers, starting with the more frequent character type.
If the counts are equal, you can start with either letters or numbers; it doesn't matter.
As you build the new string, pull the appropriate characters (either a letter or a number) from the original string in sequence.
If at any point you run out of characters of one type, it means you won't be able to maintain the alternating pattern. This indicates that there is no solution so stop building the new string.
Return the newly created, rearranged string, or an empty string if no valid rearrangement is possible.

Code Implementation

def reformat_string(input_string):
    letters = []
    digits = []
    for char in input_string:
        if char.isalpha():
            letters.append(char)
        elif char.isdigit():
            digits.append(char)

    number_of_letters = len(letters)
    number_of_digits = len(digits)

    # If the difference is too big, it's impossible to reformat.
    if abs(number_of_letters - number_of_digits) > 1:
        return ""

    reformatted_string = ""

    # Determine which type to start with.
    if number_of_letters >= number_of_digits:
        letter_index = 0
        digit_index = 0

        # Interweave letters and digits.
        while letter_index < number_of_letters or digit_index < number_of_digits:
            if letter_index < number_of_letters:
                reformatted_string += letters[letter_index]
                letter_index += 1
            if digit_index < number_of_digits:
                reformatted_string += digits[digit_index]
                digit_index += 1
    else:
        letter_index = 0
        digit_index = 0

        # Interweave digits and letters.
        while letter_index < number_of_letters or digit_index < number_of_digits:
            if digit_index < number_of_digits:
                reformatted_string += digits[digit_index]
                digit_index += 1
            
            #Ensure that there are still letters to add
            if letter_index < number_of_letters:
                reformatted_string += letters[letter_index]
                letter_index += 1

    # After the interleaving is complete, the new string is returned
    return reformatted_string

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input string 's' of length n once to count the number of letters and digits. It then iterates through the string again, at most once, to construct the reformatted string. Thus, the time complexity is dominated by these linear traversals, resulting in O(n) time complexity.

Space Complexity

O(N) – The algorithm constructs a new string to store the rearranged characters. In the worst-case scenario, where a valid rearrangement is possible, this new string will have the same length as the input string. Therefore, the auxiliary space required for the new string is proportional to the input size, N, where N is the length of the input string. Thus, the space complexity is O(N).

Edge Cases

Case	How to Handle
Null or empty input string	Return an empty string immediately as there's nothing to reformat.
String with only one character	Return the string itself as it's already trivially reformatted.
String with only digits	Return empty string if number of digits and letters have difference > 1.
String with only letters	Return empty string if number of digits and letters have difference > 1.
String with number of digits significantly exceeding number of letters	Return empty string if the absolute difference between digit count and letter count is greater than 1.
String with number of letters significantly exceeding number of digits	Return empty string if the absolute difference between digit count and letter count is greater than 1.
String with alternating digits and letters already	Return the original string as it is already in the correct format.
Large input string that could cause performance issues	Use a linear time algorithm (O(n)) based on character counting and interleaving.

Null or empty input string

How to Handle:

Return an empty string immediately as there's nothing to reformat.

String with only one character

How to Handle:

Return the string itself as it's already trivially reformatted.

String with only digits

How to Handle:

Return empty string if number of digits and letters have difference > 1.

String with only letters

How to Handle:

Return empty string if number of digits and letters have difference > 1.

String with number of digits significantly exceeding number of letters

How to Handle:

Return empty string if the absolute difference between digit count and letter count is greater than 1.

String with number of letters significantly exceeding number of digits

How to Handle:

Return empty string if the absolute difference between digit count and letter count is greater than 1.

String with alternating digits and letters already

How to Handle:

Return the original string as it is already in the correct format.

Large input string that could cause performance issues

How to Handle:

Use a linear time algorithm (O(n)) based on character counting and interleaving.

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:

What is the maximum length of the input string `s`?
Can the input string `s` be empty or null?
If it is impossible to reformat the string, should I return an empty string or null?
Does the input string `s` only contain lowercase alphanumeric characters, or can it contain other characters like spaces or special symbols?
If multiple valid reformatted strings exist, is any one of them acceptable?

Brute Force Solution

Approach

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

First, count how many letters and how many digits you have.
If the difference between the count of letters and digits is more than one, it is impossible to reformat the string, and you can stop.
If it is possible, consider two options: starting with a letter or starting with a digit.
For each option (starting with a letter or digit), try all possible arrangements where letters and digits alternate.
Check if each arrangement is valid: meaning, does it actually alternate between a letter and a digit?
If an arrangement is valid, save it.
Once you've tried all arrangements for both starting options, see if you've saved any valid arrangements.
If you have saved arrangements, pick any one of them as the result. The problem states any valid answer is okay.

Code Implementation

def reformat_string_brute_force(input_string):
    letters = [char for char in input_string if char.isalpha()]
    digits = [char for char in input_string if char.isdigit()]

    # Check if the string can be reformatted
    if abs(len(letters) - len(digits)) > 1:
        return ""

    from itertools import permutations

    # Try all possible permutations
    for permutation in permutations(letters + digits):
        reformatted_string = "".join(permutation)

        # Verify the reformatting pattern
        valid = True
        for i in range(len(reformatted_string) - 1):
            if reformatted_string[i].isalpha() == reformatted_string[i+1].isalpha():
                valid = False
                break

        if valid:
            return reformatted_string

    return ""

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, count how many letters and how many numbers are in the string.
Determine which type of character (letter or number) appears more frequently.
If the difference in counts between letters and numbers is more than 1, it's impossible to rearrange the string as requested, so indicate that there's no solution.
Otherwise, create a new string by alternating letters and numbers, starting with the more frequent character type.
If the counts are equal, you can start with either letters or numbers; it doesn't matter.
As you build the new string, pull the appropriate characters (either a letter or a number) from the original string in sequence.
If at any point you run out of characters of one type, it means you won't be able to maintain the alternating pattern. This indicates that there is no solution so stop building the new string.
Return the newly created, rearranged string, or an empty string if no valid rearrangement is possible.

Code Implementation

def reformat_string(input_string):
    letters = []
    digits = []
    for char in input_string:
        if char.isalpha():
            letters.append(char)
        elif char.isdigit():
            digits.append(char)

    number_of_letters = len(letters)
    number_of_digits = len(digits)

    # If the difference is too big, it's impossible to reformat.
    if abs(number_of_letters - number_of_digits) > 1:
        return ""

    reformatted_string = ""

    # Determine which type to start with.
    if number_of_letters >= number_of_digits:
        letter_index = 0
        digit_index = 0

        # Interweave letters and digits.
        while letter_index < number_of_letters or digit_index < number_of_digits:
            if letter_index < number_of_letters:
                reformatted_string += letters[letter_index]
                letter_index += 1
            if digit_index < number_of_digits:
                reformatted_string += digits[digit_index]
                digit_index += 1
    else:
        letter_index = 0
        digit_index = 0

        # Interweave digits and letters.
        while letter_index < number_of_letters or digit_index < number_of_digits:
            if digit_index < number_of_digits:
                reformatted_string += digits[digit_index]
                digit_index += 1
            
            #Ensure that there are still letters to add
            if letter_index < number_of_letters:
                reformatted_string += letters[letter_index]
                letter_index += 1

    # After the interleaving is complete, the new string is returned
    return reformatted_string

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input string	Return an empty string immediately as there's nothing to reformat.
String with only one character	Return the string itself as it's already trivially reformatted.
String with only digits	Return empty string if number of digits and letters have difference > 1.
String with only letters	Return empty string if number of digits and letters have difference > 1.
String with number of digits significantly exceeding number of letters	Return empty string if the absolute difference between digit count and letter count is greater than 1.
String with number of letters significantly exceeding number of digits	Return empty string if the absolute difference between digit count and letter count is greater than 1.
String with alternating digits and letters already	Return the original string as it is already in the correct format.
Large input string that could cause performance issues	Use a linear time algorithm (O(n)) based on character counting and interleaving.

Null or empty input string

How to Handle:

Return an empty string immediately as there's nothing to reformat.

String with only one character

How to Handle:

Return the string itself as it's already trivially reformatted.

String with only digits

How to Handle:

Return empty string if number of digits and letters have difference > 1.

String with only letters

How to Handle:

Return empty string if number of digits and letters have difference > 1.

String with number of digits significantly exceeding number of letters

How to Handle:

Return empty string if the absolute difference between digit count and letter count is greater than 1.

String with number of letters significantly exceeding number of digits

How to Handle:

Return empty string if the absolute difference between digit count and letter count is greater than 1.

String with alternating digits and letters already

How to Handle:

Return the original string as it is already in the correct format.

Large input string that could cause performance issues

How to Handle:

Use a linear time algorithm (O(n)) based on character counting and interleaving.