Skip to content

1417. Reformat The String 👍

Approach 1: Straightforward

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
 public:
  string reformat(string s) {
    vector<char> A;
    vector<char> B;

    for (const char c : s)
      isalpha(c) ? A.push_back(c) : B.push_back(c);

    if (A.size() < B.size())
      swap(A, B);
    if (A.size() - B.size() > 1)
      return "";

    string ans;

    for (int i = 0; i < B.size(); ++i)
      ans += string{A[i], B[i]};

    if (A.size() > B.size())
      ans += A.back();
    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
  public String reformat(String s) {
    List<Character> A = new ArrayList<>();
    List<Character> B = new ArrayList<>();

    for (final char c : s.toCharArray())
      if (Character.isAlphabetic(c))
        A.add(c);
      else
        B.add(c);

    if (A.size() < B.size()) {
      List<Character> temp = A;
      A = B;
      B = temp;
    }
    if (A.size() - B.size() > 1)
      return "";

    StringBuilder sb = new StringBuilder();

    for (int i = 0; i < B.size(); ++i) {
      sb.append(A.get(i));
      sb.append(B.get(i));
    }

    if (A.size() > B.size())
      sb.append(A.get(A.size() - 1));
    return sb.toString();
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
  def reformat(self, s: str) -> str:
    A = [c for c in s if c.isalpha()]
    B = [c for c in s if c.isdigit()]

    if len(A) < len(B):
      A, B = B, A
    if len(A) - len(B) > 1:
      return ''

    ans = []

    for i in range(len(B)):
      ans.append(A[i])
      ans.append(B[i])

    if len(A) == len(B) + 1:
      ans.append(A[-1])
    return ''.join(ans)

Approach 2: In-place

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
 public:
  string reformat(string s) {
    const int countAlpha =
        ranges::count_if(s, [](char c) { return isalpha(c); });
    const int countDigit = s.size() - countAlpha;
    if (abs(countAlpha - countDigit) >= 2)
      return "";

    // Initialize the starting index. e.g. "a0a0a" or "0a0a0".
    const int alphaStartingIndex = countAlpha >= countDigit ? 0 : 1;

    // Place all alphas in the indices 0, 2, 4, 6, ... or 1, 3, 5, 7, ....
    for (int i = 0, j = alphaStartingIndex; i < s.length(); ++i) {
      if (i < j && i % 2 == alphaStartingIndex)
        continue;  // The `s[i]` has been set.
      if (!isalpha(s[i]))
        continue;
      swap(s[i], s[j]);
      j += 2;
      --i;
    }

    return s;
  }
};