1417. Reformat The String
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:
- We first split the input string into two lists: one containing all the letters and the other containing all the digits.
- 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.
- 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.
- We then initialize an empty list
ans
to build the reformatted string. - We iterate over both lists simultaneously, taking one letter and one digit at a time and appending them alternately to
ans
. - 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
. - 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:
-
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 tob
.a = [c for c in s if c.islower()] b = [c for c in s if c.isdigit()]
-
Checking Possibility: We compute the difference between the lengths of
a
andb
usingabs(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.if abs(len(a) - len(b)) > 1: return ''
-
Arranging the Characters:
- If there are more digits than letters, we swap
a
andb
so thata
always contains the longer list. - The zip function is used to iterate over pairs of characters from
a
andb
. In each iteration, we take one character from each list and append them toans
, ensuring that they alternate in the final string.
if len(a) < len(b): a, b = b, a ans = [] for x, y in zip(a, b): ans.append(x + y)
- If there are more digits than letters, we swap
-
Handling the Remainder: If
a
is longer thanb
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 froma
toans
.if len(a) > len(b): ans.append(a[-1])
-
Creating the Final String:
- Lastly, we join the list
ans
into a string using''.join(ans)
and return it.
return ''.join(ans)
- Lastly, we join the list
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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's assume we have an input string s
= "a1b2c".
Following the solution approach:
-
Separating Characters:
- We create two lists, where
a = ['a', 'b', 'c']
extracts the letters andb = ['1', '2']
extracts the digits.
a = ['a', 'b', 'c'] b = ['1', '2']
- We create two lists, where
-
Checking Possibility:
- We calculate the difference in lengths. Here,
len(a) = 3
andlen(b) = 2
. The difference is1
, which is allowable. - Since the difference is not more than 1, we can proceed.
- We calculate the difference in lengths. Here,
-
Arranging the Characters:
-
Since
a
is not shorter thanb
, there is no need to swap. -
We iterate using
zip
to take one character from each list and create pairs:ans = [] for x, y in zip(a, b): ans.append(x) ans.append(y) # Now, ans = ['a', '1', 'b', '2']
-
-
Handling the Remainder:
-
Because
a
is longer thanb
by one, we have one extra character 'c' froma
. We append it to the listans
.ans.append('c') # The updated ans is ['a', '1', 'b', '2', 'c']
-
-
Creating the Final String:
- We join
ans
into a string, resulting in "a1b2c".
return ''.join(ans) # Output string is "a1b2c"
- We join
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.
Solution Implementation
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
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
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
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.
Learn more about how to find time and space complexity quickly using problem constraints.
How does merge sort divide the problem into subproblems?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Donāt Miss This!