1417. Reformat The String LeetCode Solution

In this guide, you will get 1417. Reformat The String LeetCode Solution with the best time and space complexity. The solution to Reformat The String problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

  1. Problem Statement
  2. Complexity Analysis
  3. Reformat The String solution in C++
  4. Reformat The String solution in Java
  5. Reformat The String solution in Python
  6. Additional Resources
1417. Reformat The String LeetCode Solution image

Problem Statement of Reformat The String

You are given an alphanumeric string s. (Alphanumeric string is a string consisting of lowercase English letters and digits).
You have to find a permutation of the string where no letter is followed by another letter and no digit is followed by another digit. That is, no two adjacent characters have the same type.
Return the reformatted string or return an empty string if it is impossible to reformat the string.

Example 1:

Input: s = “a0b1c2”
Output: “0a1b2c”
Explanation: No two adjacent characters have the same type in “0a1b2c”. “a0b1c2”, “0a1b2c”, “0c2a1b” are also valid permutations.

Example 2:

Input: s = “leetcode”
Output: “”
Explanation: “leetcode” has only characters so we cannot separate them by digits.

Example 3:

Input: s = “1229857369”
Output: “”
Explanation: “1229857369” has only digits so we cannot separate them by characters.

Constraints:

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

Complexity Analysis

  • Time Complexity: O(n)
  • Space Complexity: O(n)
See also  1942. The Number of the Smallest Unoccupied Chair LeetCode Solution

1417. Reformat The String LeetCode Solution in C++

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;
  }
};
/* code provided by PROGIEZ */

1417. Reformat The String LeetCode Solution in Java

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();
  }
}
// code provided by PROGIEZ

1417. Reformat The String LeetCode Solution in Python

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)
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Similar: