algoadvance

Leetcode 1417. Reformat The String

Problem Statement

The problem is to reformat a given string so that no two adjacent characters are of the same type. Specifically, the string consists of lowercase alphabetic characters and digits. We need to rearrange the characters such that letters and digits alternate. If it is impossible to rearrange the string in this fashion, return an empty string.

Example

  1. Input: s = "a0b1c2" Output: "0a1b2c"
  2. Input: s = "leetcode" Output: "" (since there are no digits)
  3. Input: s = "1229857369" Output: "" (since there are no letters)
  4. Input: s = "covid2019" Output: "c2o0v1i9d"

Clarifying Questions

  1. What is the maximum length of the input string?
    • This helps to understand the possible time and space complexity involved.
  2. Are there any guarantees about the input string’s content other than it containing only lowercase letters and digits?
    • Ensuring there are strictly no other character types.
  3. Do we need to care about the stability of characters (i.e., should the original order be maintained as much as possible)?
    • Helps in deciding the algorithm’s approach.

Strategy

  1. Counting Occurrences: First, count the number of letters and digits.
  2. Feasibility Check: Check if the absolute difference between the number of letters and digits is greater than 1. If so, return an empty string because it’s impossible to alternate them correctly.
  3. Split Characters: Separate letters and digits into two different containers.
  4. Reordering Logic: Depending on which type of character (letters or digits) is in the majority, start with that type and alternate with the other type.
  5. Building the Result: Construct the result by alternating characters from the two containers.

Code

#include <string>
#include <vector>
#include <algorithm>

std::string reformat(std::string s) {
    std::vector<char> letters, digits;
    
    // Separate the characters into letters and digits
    for (char c : s) {
        if (std::isalpha(c)) {
            letters.push_back(c);
        } else {
            digits.push_back(c);
        }
    }
    
    // Check if reformatting is possible
    if (std::abs((int)(letters.size() - digits.size())) > 1) {
        return "";
    }
    
    // Resultant reformatted string
    std::string result;
    result.reserve(s.length());
    
    // Determine which type to start with
    bool lettersFirst = letters.size() > digits.size();
    
    // Alternate characters
    auto lit = letters.begin();
    auto dit = digits.begin();
    while (lit != letters.end() || dit != digits.end()) {
        if (lettersFirst && lit != letters.end()) {
            result.push_back(*lit++);
        }
        if (!lettersFirst && dit != digits.end()) {
            result.push_back(*dit++);
        }
        lettersFirst = !lettersFirst;
    }
    
    return result;
}

Time Complexity

By following this strategy and utilizing efficient separation and alternating logic, we ensure the solution is both clear and optimal.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI