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 <= 500s consists of only lowercase English letters and/or digits.program main
implicit none
character(len=:), allocatable :: s
character(len=:), allocatable :: result
s = "a0b1c2"
write(*,*) "Input: ", s
result = solve(s)
write(*,*) "Output: ", result
s = "leetcode"
write(*,*) "Input: ", s
result = solve(s)
write(*,*) "Output: ", result
s = "1229857369"
write(*,*) "Input: ", s
result = solve(s)
write(*,*) "Output: ", result
contains
function solve(s) result(result)
implicit none
character(len=*), intent(in) :: s
character(len=:), allocatable :: result
integer :: i, j
allocate(character(len=size(s)) :: result)
do i = 1, size(s)
select case (s(i:i))
case ("0":"9")
result(i:i) = s(i:i)
case default
do j = 1, size(s)
if (s(j:j) == s(i:i)) exit
end do
if (j > size(s)) then
deallocate(result)
result = ""
return
end if
result(i:i) = s(j:j)
end select
end do
end function solve
end program maintemp.f95:30:36:
30 | allocate(character(len=size(s)) :: result)
| 1
Error: ‘array’ argument of ‘size’ intrinsic at (1) must be an array
temp.f95:36:35:
36 | do j = 1, size(s)
| 1
Error: ‘array’ argument of ‘size’ intrinsic at (1) must be an array
temp.f95:39:33:
39 | if (j > size(s)) then
| 1
Error: ‘array’ argument of ‘size’ intrinsic at (1) must be an array
temp.f95:31:23:
31 | do i = 1, size(s)
| 1
Error: ‘array’ argument of ‘size’ intrinsic at (1) must be an array
program main
implicit none
character(len=500) :: s
character(len=500) :: result
integer :: i, j
! Read input
read(*,*) s
! Initialize result
result = ""
! Check if the string is alphanumeric
if (index(s, "0123456789") == 0 .and. index(s, "abcdefghijklmnopqrstuvwxyz") == 0) then
write(*,*) ""
return
end if
! Find the first character that is not a digit or a letter
i = 1
do while (i <= len(s) .and. (s(i:i) >= "0" .and. s(i:i) <= "9" .or. s(i:i) >= "a" .and. s(i:i) <= "z"))
i = i + 1
end do
! Check if the string is already in the correct format
if (i == len(s) + 1) then
write(*,*) s
return
end if
! Find the first character that is a digit or a letter
j = i
do while (j <= len(s) .and. (s(j:j) >= "0" .and. s(j:j) <= "9" .or. s(j:j) >= "a" .and. s(j:j) <= "z"))
j = j + 1
end do
! Check if the string is already in the correct format
if (j == len(s) + 1) then
write(*,*) s
return
end if
! Separate the string into two parts
result = s(i:j-1)
s = s(j:len(s))
! Recursively solve the problem for the remaining string
call solve(s, result)
contains
subroutine solve(s, result)
implicit none
character(len=500) :: s
character(len=500) :: result
integer :: i, j
! Check if the string is alphanumeric
if (index(s, "0123456789") == 0 .and. index(s, "abcdefghijklmnopqrstuvwxyz") == 0) then
write(*,*) result // s
return
end if
! Find the first character that is not a digit or a letter
i = 1
do while (i <= len(s) .and. (s(i:i) >= "0" .and. s(i:i) <= "9" .or. s(i:i) >= "a" .and. s(i:i) <= "z"))
i = i + 1
end do
! Check if the string is already in the correct format
if (i == len(s) + 1) then
write(*,*) result // s
return
end if
! Find the first character that is a digit or a letter
j = i
do while (j <= len(s) .and. (s(j:j) >= "0" .and. s(j:j) <= "9" .or. s(j:j) >= "a" .and. s(j:j) <= "z"))
j = j + 1
end do
! Check if the string is already in the correct format
if (j == len(s) + 1) then
write(*,*) result // s
return
end if
! Separate the string into two parts
result = result // s(i:j-1)
s = s(j:len(s))
! Recursively solve the problem for the remaining string
call solve(s, result)
end subroutine solve
end program main
temp.f95:97:21:
97 | call solve(s, result)
| 1
Error: SUBROUTINE ‘solve’ at (1) cannot be called recursively, as it is not RECURSIVE
from collections import deque
def reformat(s: str) -> str:
letters, digits = deque(), deque()
for c in s:
if c.isalpha():
letters.append(c)
else:
digits.append(c)
if abs(len(letters) - len(digits)) > 1:
return ""
result = []
use_letter = len(letters) > len(digits)
while letters or digits:
if use_letter:
result.append(letters.popleft())
else:
result.append(digits.popleft())
use_letter = not use_letter
return ''.join(result)
The algorithm first separates the input string s into two queues, letters and digits. This can be done by iterating through the input string s and checking if each character is a letter or digit. Then it checks if the difference between the number of letters and digits is greater than 1. If so, it returns an empty string as it is impossible to reformat the string with no two adjacent characters having the same type.
If the difference is not greater than 1, the algorithm initializes an empty result string or list. Then, it checks which type (letter or digit) has more elements, and iterates through the queues, alternating between types (letters and digits) and inserting the next character of the current type into the result. This ensures no two adjacent characters have the same type. Finally, the algorithm returns the result in the appropriate type (string or list, depending on the language).
The algorithm's complexity is O(n), where n is the length of the input string s.
#include <string>
#include <queue>
std::string reformat(std::string s) {
std::queue<char> letters, digits;
for (char c : s) {
if (isalpha(c)) letters.push(c);
else digits.push(c);
}
if (abs((int)(letters.size() - digits.size())) > 1) return "";
std::string result = "";
bool use_letter = letters.size() > digits.size();
while (!letters.empty() || !digits.empty()) {
if (use_letter) {
result += letters.front();
letters.pop();
} else {
result += digits.front();
digits.pop();
}
use_letter = !use_letter;
}
return result;
}
The algorithm first separates the input string s into two queues, letters and digits. This can be done by iterating through the input string s and checking if each character is a letter or digit. Then it checks if the difference between the number of letters and digits is greater than 1. If so, it returns an empty string as it is impossible to reformat the string with no two adjacent characters having the same type.
If the difference is not greater than 1, the algorithm initializes an empty result string or list. Then, it checks which type (letter or digit) has more elements, and iterates through the queues, alternating between types (letters and digits) and inserting the next character of the current type into the result. This ensures no two adjacent characters have the same type. Finally, the algorithm returns the result in the appropriate type (string or list, depending on the language).
The algorithm's complexity is O(n), where n is the length of the input string s.