1417. Reformat The String

EasyString
Leetcode Link

Problem Description

The problem presents us with an input string s that contains only lowercase letters and digits. Our task is to rearrange the characters of s into a new string where letters and digits alternate, meaning no two letters or two digits are adjacent to each other. If such an arrangement is not possible, the function should return an empty string.

In essence, we're asked to create a pattern like letter-digit-letter-digit ... or digit-letter-digit-letter ... throughout the entire string. If there is a significant imbalance between the number of digits and letters (i.e., the count of one type exceeds the other by more than one), it is clear that reformatting in the desired way is impossible. This is because at some point, we would need to place two characters of the same type next to each other to use all characters, which is against the rules.

Intuition

The underlying intuition for the solution comes from the rule that no two adjacent characters can be of the same type (i.e., both digits or both letters). This naturally leads to the observation that if there are significantly more characters of one type than the other, the task is impossible. Specifically, if the difference in quantity between letters and digits is more than one, we cannot interleave them perfectly.

To arrive at the solution:

  1. We first split the input string into two lists: one containing all the letters and the other containing all the digits.
  2. We then check the lengths of these two lists. If the difference between their lengths is more than 1, we return an empty string since reformatting is impossible.
  3. If the list of letters is shorter than the list of digits, we swap the lists to ensure that we start and end with the character type that has more occurrences.
  4. We then initialize an empty list ans to build the reformatted string.
  5. We iterate over both lists simultaneously, taking one letter and one digit at a time and appending them alternately to ans.
  6. If there is one extra character (which will always be of the type we started with due to the earlier swapping), we append it to the end of ans.
  7. Finally, we join ans into a string and return it as the result.

In this approach, we use a greedy strategy, always placing a character of the surplus type (if there is one) at the beginning and end of the final string and then filling the middle by alternating between letters and digits.

Solution Approach

The solution uses the following algorithmic concepts and data structures:

Algorithm:

The algorithm is a greedy one, placing characters in such a way that we adhere to the alternating letter-digit pattern until we run out of characters. This approach takes advantage of the fact that as long as the number of letters and numbers are within one count of each other, a valid sequence is always possible.

Data Structures:

Two lists, a and b, are used to separate the letters and digits from the input string, respectively. An additional list, ans, is used to build the final result.

Approach Steps:

  1. Separating Characters: Using list comprehensions, we go through the string twice, once to collect all lowercase letters and add them to a, and another time for digits that are added to b.

    1a = [c for c in s if c.islower()]
    2b = [c for c in s if c.isdigit()]
  2. Checking Possibility: We compute the difference between the lengths of a and b using abs(len(a) - len(b)). If this value is more than 1, we immediately return an empty string '' as it's impossible to rearrange the characters into a valid sequence.

    1if abs(len(a) - len(b)) > 1:
    2    return ''
  3. Arranging the Characters:

    • If there are more digits than letters, we swap a and b so that a always contains the longer list.
    • The zip function is used to iterate over pairs of characters from a and b. In each iteration, we take one character from each list and append them to ans, ensuring that they alternate in the final string.
    1if len(a) < len(b):
    2    a, b = b, a
    3ans = []
    4for x, y in zip(a, b):
    5    ans.append(x + y)
  4. Handling the Remainder: If a is longer than b by one character, which can only happen if there were more letters than digits or vice versa but not more than one, we append the last remaining character from a to ans.

    1if len(a) > len(b):
    2    ans.append(a[-1])
  5. Creating the Final String:

    • Lastly, we join the list ans into a string using ''.join(ans) and return it.
    1return ''.join(ans)

In summary, the algorithm first checks for the possibility of the task, then creates a structure to hold the alternating characters, and finally constructs the required string in a greedy manner.

Example Walkthrough

Let's assume we have an input string s = "a1b2c".

Following the solution approach:

  1. Separating Characters:

    • We create two lists, where a = ['a', 'b', 'c'] extracts the letters and b = ['1', '2'] extracts the digits.
    1a = ['a', 'b', 'c']
    2b = ['1', '2']
  2. Checking Possibility:

    • We calculate the difference in lengths. Here, len(a) = 3 and len(b) = 2. The difference is 1, which is allowable.
    • Since the difference is not more than 1, we can proceed.
  3. Arranging the Characters:

    • Since a is not shorter than b, there is no need to swap.

    • We iterate using zip to take one character from each list and create pairs:

      1ans = []
      2for x, y in zip(a, b):
      3    ans.append(x)
      4    ans.append(y)
      5# Now, ans = ['a', '1', 'b', '2']
  4. Handling the Remainder:

    • Because a is longer than b by one, we have one extra character 'c' from a. We append it to the list ans.

      1ans.append('c')
      2# The updated ans is ['a', '1', 'b', '2', 'c']
  5. Creating the Final String:

    • We join ans into a string, resulting in "a1b2c".
    1return ''.join(ans)
    2# Output string is "a1b2c"

In this example, the input string was successfully rearranged to follow the pattern of letters and digits alternating, and no additional characters were left unused, satisfying the problem's requirements.

Python Solution

1class Solution:
2    def reformat(self, s: str) -> str:
3        # Extract all alphabetic characters into the list 'alphabets'
4        alphabets = [c for c in s if c.islower()]
5      
6        # Extract all numeric characters into the list 'digits'
7        digits = [c for c in s if c.isdigit()]
8      
9        # Early return an empty string if the absolute difference in counts is greater than 1
10        # This is because it would be impossible to alternate characters as required
11        if abs(len(alphabets) - len(digits)) > 1:
12            return ''
13      
14        # If there are fewer alphabets than digits, swap the lists to prepare for formatting
15        if len(alphabets) < len(digits):
16            alphabets, digits = digits, alphabets
17      
18        # Initialize an empty list to hold the reformatted string characters
19        reformatted = []
20      
21        # Iterate over the characters in both lists simultaneously using zip
22        for alpha_char, digit_char in zip(alphabets, digits):
23            # Append alternated characters to the 'reformatted' list
24            reformatted.append(alpha_char + digit_char)
25      
26        # If there's an extra character in 'alphabets', append it to the end
27        if len(alphabets) > len(digits):
28            reformatted.append(alphabets[-1])
29      
30        # Join all elements in 'reformatted' into a string and return
31        return ''.join(reformatted)
32

Java Solution

1class Solution {
2    public String reformat(String s) {
3        // StringBuilder to hold digits
4        StringBuilder digits = new StringBuilder();
5        // StringBuilder to hold letters
6        StringBuilder letters = new StringBuilder();
7      
8        // Separate digits and letters into different StringBuilder objects
9        for (char c : s.toCharArray()) {
10            if (Character.isDigit(c)) {
11                digits.append(c);
12            } else {
13                letters.append(c);
14            }
15        }
16      
17        // Get the lengths of the two StringBuilder objects
18        int digitCount = digits.length();
19        int letterCount = letters.length();
20      
21        // If the count difference is more than 1, it's impossible to reformat
22        if (Math.abs(digitCount - letterCount) > 1) {
23            return "";
24        }
25      
26        // StringBuilder to hold the final reformatted string
27        StringBuilder reformatted = new StringBuilder();
28      
29        // Build the reformatted string by alternating between the groups
30        for (int i = 0; i < Math.min(digitCount, letterCount); ++i) {
31            // Check which group has more characters and append accordingly
32            if (digitCount > letterCount) {
33                reformatted.append(digits.charAt(i));
34                reformatted.append(letters.charAt(i));
35            } else {
36                reformatted.append(letters.charAt(i));
37                reformatted.append(digits.charAt(i));
38            }
39        }
40      
41        // Add the extra character at the end if counts are not equal
42        if (digitCount > letterCount) {
43            reformatted.append(digits.charAt(digitCount - 1));
44        }
45        if (digitCount < letterCount) {
46            reformatted.append(letters.charAt(letterCount - 1));
47        }
48      
49        // Return the final reformatted string
50        return reformatted.toString();
51    }
52}
53

C++ Solution

1class Solution {
2public:
3    // Function to reformat the string such that digits and letters alternate,
4    // and if it's not possible, return an empty string.
5    string reformat(string s) {
6        string digits = "", letters = "";
7        // Separate digits and letters into two different strings.
8        for (char c : s) {
9            if (isdigit(c)) {
10                digits += c;
11            } else {
12                letters += c;
13            }
14        }
15
16        int digitCount = digits.size(), letterCount = letters.size();
17      
18        // If the difference in count between digits and letters is more than 1,
19        // it's not possible to alternate.
20        if (abs(digitCount - letterCount) > 1) return "";
21
22        string result = "";
23      
24        // Interleave the characters from both strings.
25        for (int i = 0; i < min(digitCount, letterCount); ++i) {
26            // If there are more digits, start with a digit; otherwise, start with a letter.
27            if (digitCount > letterCount) {
28                result += digits[i];
29                result += letters[i];
30            } else {
31                result += letters[i];
32                result += digits[i];
33            }
34        }
35
36        // If there's an extra character in one of the strings, append it to the result.
37        if (digitCount > letterCount) result += digits[digitCount - 1];
38        if (digitCount < letterCount) result += letters[letterCount - 1];
39
40        return result;
41    }
42};
43

Typescript Solution

1// Function to separate digits and alphabetic characters from a string.
2function separateDigitsAndLetters(s: string): { digits: string; letters: string } {
3    // Initialize empty strings for digits and letters.
4    let digits = '';
5    let letters = '';
6
7    // Iterate through each character of the string.
8    s.split('').forEach(char => {
9        // If the character is a digit, add it to the digits string.
10        // Otherwise, add it to the letters string.
11        if (!isNaN(parseInt(char))) {
12            digits += char;
13        } else {
14            letters += char;
15        }
16    });
17
18    // Return an object containing separated digits and letters.
19    return { digits, letters };
20}
21
22// Function to check if reformatting is possible based on the counts of digits and letters.
23function canReformat(digitCount: number, letterCount: number): boolean {
24    // Reformatting is not possible if the count difference is more than 1.
25    return Math.abs(digitCount - letterCount) <= 1;
26}
27
28// Helper function to interleave characters from digits and letters.
29function interleaveCharacters(
30    digits: string,
31    letters: string,
32    longerCount: number,
33    shorterCount: number
34): string {
35    let result = '';
36
37    // Interleave characters from both strings until one of them runs out.
38    for (let i = 0; i < shorterCount; ++i) {
39        // Append characters from the string with more characters first.
40        if (longerCount === digits.length) {
41            result += digits[i];
42        }
43        // Append characters from the other string next.
44        result += letters[i];
45        // Append characters from the string with fewer characters last (if not yet appended).
46        if (longerCount !== digits.length) {
47            result += digits[i];
48        }
49    }
50
51    // Add the last remaining character if there is an extra in one of the strings.
52    if (longerCount !== shorterCount) {
53        result += longerCount === digits.length ? digits[shorterCount] : letters[shorterCount];
54    }
55
56    return result;
57}
58
59// Main function to reformat the string such that digits and letters alternate.
60function reformat(s: string): string {
61    // Use the separateDigitsAndLetters function to get digits and letters.
62    const { digits, letters } = separateDigitsAndLetters(s);
63
64    // Get the counts of digits and letters.
65    const digitCount = digits.length;
66    const letterCount = letters.length;
67
68    // If reformatting is not possible, return an empty string.
69    if (!canReformat(digitCount, letterCount)) {
70        return '';
71    }
72
73    // Determine which string has more characters.
74    const longerCount = Math.max(digitCount, letterCount);
75    const shorterCount = Math.min(digitCount, letterCount);
76
77    // Use the interleaveCharacters helper function to create the reformatted string.
78    return interleaveCharacters(digits, letters, longerCount, shorterCount);
79}
80

Time and Space Complexity

The time complexity of the given code is O(n), where n is the length of the input string s. This is because the code iterates through the string twice: once to create the list of letters a and once to create the list of digits b. Each of these operations is O(n). The zip operation inside the for loop and the conditionals outside and inside the loop do not change the overall time complexity, which remains linear with respect to the size of the input.

The space complexity is also O(n). We create two lists, a and b, which together hold all characters from the string s. In the worst case, where all characters are either digits or letters, both lists would be about half the length of s, so the space used by these lists scales linearly with the length of s. The ans list will at most hold the same number of characters as s, further contributing to the linear space complexity. The space required for the variables and the single characters added in each iteration is negligible compared to the space used by the lists.


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 👨‍🏫