Perform String Shifts

🏠 ⬅️ ➡️

You are given a string s containing lowercase English letters, and a matrix shift, where shift[i] = [directioni, amounti]:

  • directioni can be 0 (for left shift) or 1 (for right shift).
  • amounti is the amount by which string s is to be shifted.
  • A left shift by 1 means remove the first character of s and append it to the end.
  • Similarly, a right shift by 1 means remove the last character of s and add it to the beginning.

Return the final string after all operations.

Example 1:

Input: s = "abc ", shift = [[0,1],[1,2]] Output: "cab " Explanation: [0,1] means shift to left by 1. "abc " -> "bca " [1,2] means shift to right by 2. "bca " -> "cab "

Example 2:

Input: s = "abcdefg ", shift = [[1,1],[1,1],[0,2],[1,3]] Output: "efgabcd " Explanation:
[1,1] means shift to right by 1. "abcdefg " -> "gabcdef " [1,1] means shift to right by 1. "gabcdef " -> "fgabcde " [0,2] means shift to left by 2. "fgabcde " -> "abcdefg " [1,3] means shift to right by 3. "abcdefg " -> "efgabcd "

Constraints:

  • 1 <= s.length <= 100
  • s only contains lower case English letters.
  • 1 <= shift.length <= 100
  • shift[i].length == 2
  • directioni is either 0 or 1.
  • 0 <= amounti <= 100
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    integer :: i, j, n
    character(len=:), allocatable :: s
    integer, dimension(:,:), allocatable :: shift

    ! read input
    read(*,*) s
    read(*,*) n
    allocate(shift(n,2))
    do i = 1, n
        read(*,*) shift(i,:)
    end do

    ! solve problem
    call solve(s, shift)

    ! print output
    write(*,'(a)') s

contains

    subroutine solve(s, shift)
        implicit none
        character(len=:), allocatable :: s
        integer, dimension(:,:), allocatable :: shift
        integer :: i, direction, amount

        do i = 1, size(shift,1)
            direction = shift(i,1)
            amount = shift(i,2)
            if (direction == 0) then
                call left_shift(s, amount)
            else
                call right_shift(s, amount)
            end if
        end do
    end subroutine solve

    subroutine left_shift(s, amount)
        implicit none
        character(len=:), allocatable :: s
        integer :: amount
        character(len=:), allocatable :: tmp

        allocate(tmp, source=s(2:))
        deallocate(s)
        allocate(s, source=' '//tmp)
        deallocate(tmp)
    end subroutine left_shift

    subroutine right_shift(s, amount)
        implicit none
        character(len=:), allocatable :: s
        integer :: amount
        character(len=:), allocatable :: tmp

        allocate(tmp, source=s(1:size(s)-1))
        deallocate(s)
        allocate(s, source=tmp//' ')
        deallocate(tmp)
    end subroutine right_shift

end program main
❌ Compiled
❌ Executed
❌ Correct 
module shift_string

implicit none

contains

function shift_string(s, shift) result(final_string)

! Declare the string and matrix types
type(string_type) :: s
type(matrix_type) :: shift
type(string_type) :: final_string

! Declare the variables
integer :: i, j, direction, amount
character(len=:), allocatable :: temp_string

! Initialize the final string
final_string = s

! Loop through each shift operation
do i = 1, size(shift, 1)

    ! Get the direction and amount of the current shift operation
    direction = shift(i, 1)
    amount = shift(i, 2)

    ! Perform the shift operation
    if (direction == 0) then ! Left shift
        temp_string = final_string%get_substring(amount+1, final_string%length()) // &
            final_string%get_substring(1, amount)
    else ! Right shift
        temp_string = final_string%get_substring(final_string%length()-amount+1, final_string%length()) // &
            final_string%get_substring(1, final_string%length()-amount)
    end if

    ! Update the final string
    final_string = temp_string

end do

end function shift_string

end module shift_string

! Test the shift_string function with the given examples
program test_shift_string

use shift_string

implicit none

! Examples
type(string_type) :: s
type(matrix_type) :: shift
type(string_type) :: final_string

! Example 1
s = string_type("abc ")
shift = matrix_type([[0, 1], [1, 2]])
final_string = shift_string(s, shift)
write (*, *) "Example 1: " // final_string%get_string()

! Example 2
s = string_type("abcdefg ")
shift = matrix_type([[1, 1], [1, 1], [0, 2], [1, 3]])
final_string = shift_string(s, shift)
write (*, *) "Example 2: " // final_string%get_string()

end program test_shift_string

! Define the string and matrix types
type string_type

! Declare the string length
integer :: length

! Declare the string characters
character(len=:), allocatable :: characters

contains

! Get the string length
pure integer function get_length()

get_length = length

end function get_length

! Get the string characters
pure character(len=:), allocatable function get_characters()

get_characters = characters

end function get_characters

! Get a substring of the string
pure type(string_type) function get_substring(start, end) result(substring)

! Declare the variables
integer :: start, end

! Initialize the substring
substring = string_type("")

! Check if the start and end indices are valid
if (start < 1 .or. end > length) then
    return
end if

! Get the substring characters
substring%characters = characters(start:end)

! Set the substring length
substring%length = end - start + 1

end function get_substring

end type string_type

type matrix_type

! Declare the matrix dimensions
integer :: rows, cols

! Declare the matrix elements
integer, allocatable :: elements(:, :)

contains

! Get the matrix dimensions
pure integer function get_dimensions() result(dimensions)

dimensions = rows

end function get_dimensions

! Get a matrix element
pure integer function get_element(row, col) result(element)

! Declare the variables
integer :: row, col

! Check if the row and column indices are valid
if (row < 1 .or. row > rows .or. col < 1 .or. col > cols) then
    element = 0
    return
end if

! Get the matrix element
element = elements(row, col)

end function get_element

end type matrix_type
🌐 Data from online sources 
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def inorder(root):
    output = []
    stack = []
    current = root

    while current or stack:
        while current:
            stack.append(current)
            current = current.left
        current = stack.pop()
        output.append(current.val)
        current = current.right

    return output

def getAllElements(root1, root2):
    tree1 = inorder(root1)
    tree2 = inorder(root2)
    result = []
    i, j = 0, 0

    while i < len(tree1) or j < len(tree2):
        if i < len(tree1) and (j >= len(tree2) or tree1[i] <= tree2[j]):
            result.append(tree1[i])
            i += 1
        else:
            result.append(tree2[j])
            j += 1

    return result
  1. Create a helper function, inorder, which takes a root node and returns the inorder traversal of the tree, in the form of an array/vector/list.
  2. The inorder function uses a stack and a while loop to iterate through each node. It starts with the left-most node and iterates through to the right-most node.
  3. Call the inorder function on both root1 and root2 and store the results in two separate arrays.
  4. Initialize two pointers i and j and iterate through both arrays together.
  5. Compare the current element of both arrays, and push the smaller element onto the result array, incrementing the corresponding pointer.
  6. If one array reaches the end, push the remaining elements from the other array to the result array.
  7. Return the result array containing the sorted elements from both trees.
🌐 Data from online sources 
#include <vector>
#include <stack>

using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
};

void inorder(TreeNode* root, vector<int>& output) {
    stack<TreeNode*> s;
    TreeNode* current = root;

    while (current || !s.empty()) {
        while (current) {
            s.push(current);
            current = current->left;
        }
        current = s.top();
        s.pop();
        output.push_back(current->val);
        current = current->right;
    }
}

vector<int> getAllElements(TreeNode* root1, TreeNode* root2) {
    vector<int> tree1, tree2;
    inorder(root1, tree1);
    inorder(root2, tree2);

    vector<int> result;
    int i = 0, j = 0;
    while (i < tree1.size() || j < tree2.size()) {
        if (i < tree1.size() && (j >= tree2.size() || tree1[i] <= tree2[j])) {
            result.push_back(tree1[i++]);
        } else {
            result.push_back(tree2[j++]);
        }
    }

    return result;
}
  1. Create a helper function, inorder, which takes a root node and returns the inorder traversal of the tree, in the form of an array/vector/list.
  2. The inorder function uses a stack and a while loop to iterate through each node. It starts with the left-most node and iterates through to the right-most node.
  3. Call the inorder function on both root1 and root2 and store the results in two separate arrays.
  4. Initialize two pointers i and j and iterate through both arrays together.
  5. Compare the current element of both arrays, and push the smaller element onto the result array, incrementing the corresponding pointer.
  6. If one array reaches the end, push the remaining elements from the other array to the result array.
  7. Return the result array containing the sorted elements from both trees.