Leetcode – Reformat The String Solution

Spread the love

The “Reformat The String” problem on Leetcode is an interesting challenge that offers an opportunity to work with strings and conditionals in Python. This extensive article will take you through the problem, exploring different approaches, and understanding their trade-offs.

Table of Contents

  1. Problem Statement & Constraints
  2. Initial Thoughts
  3. Brute-Force Approach
  4. Optimized Solution
  5. Time and Space Complexity Analysis
  6. Test Cases and Edge Cases
  7. Conclusion

1. Problem Statement & Constraints

You are given a string s containing alphanumeric characters. The task is to reformat the string in such a way that no two adjacent characters are the same type, i.e., no two adjacent letters are letters, and no two adjacent digits are digits. If it is not possible, return an empty string.

Constraints and Assumptions

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

2. Initial Thoughts

The task boils down to separating the characters into digits and letters and then alternating between them. One immediate insight is that if the count of letters and digits differ by more than 1, reformatting will be impossible.

3. Brute-Force Approach

The simplest way to solve the problem is to separate the string into two lists: one containing the letters and the other containing the digits. Once separated, check if they differ by more than one, and then combine them.

Python Code:

def reformat(s):
    letters = [ch for ch in s if ch.isalpha()]
    digits = [ch for ch in s if ch.isdigit()]
    
    if abs(len(letters) - len(digits)) > 1:
        return ""
    
    res = []
    if len(letters) >= len(digits):
        for l, d in zip(letters, digits):
            res.extend([l, d])
        res.append(letters[-1] if len(letters) > len(digits) else "")
    else:
        for l, d in zip(letters, digits):
            res.extend([d, l])
        res.append(digits[-1] if len(digits) > len(letters) else "")
    
    return "".join(res).strip()

4. Optimized Solution

The optimized solution is actually not too different from the brute-force one due to the simplicity of the problem. But we could make it a bit cleaner.

Python Code:

def reformat(s):
    letters = [ch for ch in s if ch.isalpha()]
    digits = [ch for ch in s if ch.isdigit()]
    
    if abs(len(letters) - len(digits)) > 1:
        return ""
    
    if len(digits) > len(letters):
        letters, digits = digits, letters
    
    res = []
    for l, d in zip(letters, digits):
        res.extend([l, d])
    
    if len(letters) > len(digits):
        res.append(letters[-1])
    
    return "".join(res)

5. Time and Space Complexity Analysis

Both the brute-force and the optimized solutions have the same time complexity of O(n), where n is the length of the string. The space complexity is also O(n) due to the additional arrays used for storing letters and digits.

6. Test Cases and Edge Cases

  • s = "ab123" should return "a1b2", "a1b3", or any other valid reformatted string.
  • s = "abc" should return an empty string because it does not contain any digits.
  • s = "aaa111" should return "a1a1a1"

7. Conclusion

The “Reformat The String” problem offers an excellent practice ground for working with strings and list comprehensions. The problem is simple yet elegant and teaches the importance of understanding the constraints and using Python’s built-in functions effectively.

Leave a Reply