DI String Match

🏠 ⬅️ ➡️

A permutation perm of n + 1 integers of all the integers in the range [0, n] can be represented as a string s of length n where:

  • s[i] == 'I' if perm[i] < perm[i + 1], and
  • s[i] == 'D' if perm[i] > perm[i + 1].

Given a string s, reconstruct the permutation perm and return it. If there are multiple valid permutations perm, return any of them.

Example 1:

Input: s = "IDID" Output: [0,4,1,3,2]

Example 2:

Input: s = "III" Output: [0,1,2,3]

Example 3:

Input: s = "DDI" Output: [3,2,0,1]

Constraints:

  • 1 <= s.length <= 105
  • s[i] is either 'I' or 'D'.
Note: This problem is from LeetCode.
✅ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    integer :: i, j, k, n
    character(len=1) :: s(105)
    integer :: perm(105)

    ! read input
    read(*,*) n
    read(*,*) s

    ! solve problem
    do i = 1, n
        perm(i) = i - 1
    end do
    do i = 1, n - 1
        if (s(i) == 'I') then
            j = perm(i)
            k = perm(i + 1)
            perm(i) = k
            perm(i + 1) = j
        else if (s(i) == 'D') then
            j = perm(i)
            k = perm(i + 1)
            perm(i) = k
            perm(i + 1) = j
        end if
    end do

    ! print output
    write(*,*) perm

end program main
❌ Compiled
❌ Executed
❌ Correct 
module permutation

implicit none

contains

function reconstruct_permutation(s) result(perm)

integer, intent(in) :: s(:)
integer :: perm(size(s))

! Edge case: empty string
if (size(s) == 0) then
    perm = []
    return
endif

! Initialize permutation with identity mapping
perm = [(i, i=1,size(s))]

! Loop through string and update permutation accordingly
do i=1,size(s)
    if (s(i) == 'I') then
        ! Swap adjacent elements if they are in decreasing order
        if (perm(i) > perm(i+1)) then
            call swap(perm(i), perm(i+1))
        endif
    else
        ! Swap adjacent elements if they are in increasing order
        if (perm(i) < perm(i+1)) then
            call swap(perm(i), perm(i+1))
        endif
    endif
enddo

end function reconstruct_permutation

subroutine swap(a, b)

integer, intent(inout) :: a, b
integer :: temp

temp = a
a = b
b = temp

end subroutine swap

end module permutation

program test

use permutation
implicit none

! Test case 1:
call test_case(["IDID"], [0,4,1,3,2])

! Test case 2:
call test_case(["III"], [0,1,2,3])

! Test case 3:
call test_case(["DDI"], [3,2,0,1])

contains

subroutine test_case(s, expected)

character(len=*), intent(in) :: s
integer, intent(in) :: expected(:)

integer :: perm(size(expected))

perm = reconstruct_permutation(s)

if (any(perm /= expected)) then
    write (*,*) "Error:", s, "should be", expected, "but was", perm
endif

end subroutine test_case

end program test
🌐 Data from online sources 
def isPalindrome(num):
    return str(num) == str(num)[::-1]

def superpalindromesInRange(left: str, right: str) -> int:
    l = int(left)
    r = int(right)
    cnt = 0
    base = 1
    while base * base <= r:
        if isPalindrome(base) and isPalindrome(base * base):
            if base * base >= l:
                cnt += 1
        base += 1
    return cnt

To solve the problem, we will do the following steps:
  1. Create a helper function isPalindrome to check if a given number is a palindrome.
  2. Iterate over all the possible palindrome base numbers. For each base, check if the base and the square of the base are both palindromes. If they are, check if the square of the base is within the range [l, r] and increment a counter for each valid super-palindrome found.
  3. Return the counter as the final result.
🌐 Data from online sources 
bool isPalindrome(long num) {
    string str = to_string(num);
    string revStr = str;
    reverse(revStr.begin(), revStr.end());
    return str == revStr;
}

int superpalindromesInRange(string left, string right) {
    long l = stol(left);
    long r = stol(right);
    int cnt = 0;
    for (long base = 1; base * base <= r; ++base) {
        if (isPalindrome(base) && isPalindrome(base * base)) {
            if (base * base >= l) {
                cnt++;
            }
        }
    }
    return cnt;
}

To solve the problem, we will do the following steps:
  1. Create a helper function isPalindrome to check if a given number is a palindrome.
  2. Iterate over all the possible palindrome base numbers. For each base, check if the base and the square of the base are both palindromes. If they are, check if the square of the base is within the range [l, r] and increment a counter for each valid super-palindrome found.
  3. Return the counter as the final result.