function mergeAlternately(word1: string, word2: string): string {
    // stringを配列化する
    const chars1 = word1.split('');
    const chars2 = word2.split('');

    // 文字数が多い方の長さを取得する
    const length = Math.max(chars1.length, chars2.length);

    // 交互に入れて最後にjoinする
    return Array.from({ length }).flatMap((_, i) => [chars1[i], chars2[i]]).join('');
};

function gcdOfStrings(str1: string, str2: string): string {
    // str1がstr2より長ければ反転して再帰する
    if (str1.length > str2.length) {
        return gcdOfStrings(str2, str1);
    }

    // str2がstr1で始まらない場合、共通の文字はないので最大公約文字列はないので''を返す
    if (!str2.startsWith(str1)) {
        return '';
    }

    // str1とstr2が同じ場合、str1は最大公約文字列となる
    if (str1 === str2) {
        return str1;
    }

    // str2がstr1より長い場合、str1を取り除いて再帰する。
    return gcdOfStrings(str1, str2.slice(str1.length));
};

function kidsWithCandies(candies: number[], extraCandies: number): boolean[] {
    // 既存のキャンディの中で最も多い値を求める
    const maxCandies = Math.max(...candies);

    // 既存のキャンディと追加のキャンディを足した値が最も多い値となるか判定し、配列に格納する
    return candies.map(candy => candy + extraCandies >= maxCandies);
};

function canPlaceFlowers(flowerbed: number[], n: number): boolean {
    // 両端を0でパディング
    flowerbed = [0, ...flowerbed, 0];

    // forループで花を植える
    for(let i = 0; i < flowerbed.length; i++) {
        //　現在の位置が0で、前後も0なら花を植える
        if (flowerbed[i] === 0 && flowerbed[i - 1] === 0 && flowerbed[i + 1] === 0) {
            flowerbed[i] = 1; //花を植える
            n--;
        }

        // 残りの花の数が0なら終了
        if (n === 0) {
            return true;
        }
    }

    // 最終的にn以上以上の数を植えられる（nがマイナス）ならtrue、そうでなければfalse
    return n <= 0;
};

function reverseVowels(s: string): string {
    // 母音を集める
    const vowels = 'aeiouAEIOU';

    // 文字列を分解し、母音だけを残し、残ったものを反転する
    const reversedVowelsInS = s.split('').filter((ch) => vowels.includes(ch)).reverse();

    // 元の文字列sの各文字を走査し、母音であればvowelsInSの頭から順に置き換えていき、そうでなければそのままの文字を返す
    return s.split('').map((ch) => vowels.includes(ch) ? reversedVowelsInS.shift() : ch).join('');
};

/**
 Do not return anything, modify nums in-place instead.
 */
function moveZeroes(nums: number[]): void {
    // ポインタを初期化する
    let lastNonzeroFoundAt = 0;

    // 配列を走査する
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] !== 0) {
            // 非ゼロであれば配列の前方に移動する
            nums[lastNonzeroFoundAt] = nums[i];
            // ポインタを1つ進める
            lastNonzeroFoundAt++;
        }
    }

    // 非ゼロ要素の後ろのすべての要素を0とする
    for (let i = lastNonzeroFoundAt; i < nums.length; i++) {
        nums[i] = 0;
    }
};

function isSubsequence(s: string, t: string): boolean {
    // s.length === 0 であれば、tの要素を削除していくとsとなるのでtrue
    if (s.length === 0) {
        return true;
    }

    // sのインデックスを追跡する変数iを設定する
    let i = 0;

    // tを走査する
    for (let c of t) {
        // s[i]と一致していればiを次に進める
        if (s[i] === c) {
            i++;
        }

        // s.lengthと等しければ、s要素はすべて含まれていることになるのでtrueを返す
        if (s.length === i) {
            return true;
        }
    }

    // forを抜けるとs要素に含まれていないものがあるということなのでfalseを返す
    return false;
};

function findMaxAverage(nums: number[], k: number): number {
    // k分の最初の和を計算する
    let sum = nums.slice(0, k).reduce((a, b) => a + b, 0);
    // 最大の和を初期化する
    let maxSum = sum;

    // スライディングウィンドウが配列からはみ出ないようにしながら、スライドして計算していく
    nums.slice(0, nums.length - k).reduce((prev, _, i) => {
        // 左端の要素を和から引き、右端の要素を加えてスライドして和を更新する
        sum = sum - prev + nums[i + k];

        // 最大の和を更新する
        maxSum = Math.max(maxSum, sum);

        // 左端を1つ進めてprevを更新する
        return nums[i + 1];
    }, nums[0]);

    // 最大の和をkで割って平均を求めて返す
    return maxSum / k;
};

function largestAltitude(gain: number[]): number {
    // 最初の地点の高度は0。そこから移動した高度変化量を足して移動後の高度を計算する。
    // そこと現時点での最高高度とを比較して更新する。移動後の高度を現在地点として返す。
    const [maxAltitude, _] = gain.reduce(([max, currentAltitude], diff) => {
        const newAltitude = currentAltitude + diff;
        return [Math.max(max, newAltitude), newAltitude];
    }, [0, 0])

    return maxAltitude;
};

function pivotIndex(nums: number[]): number {
    // numsの合計を計算する
    const totalSum = nums.reduce((acc, curr) => acc + curr, 0);

    // 左側の合計値の変数
    let leftSum = 0;

    // numsを走査する
    return nums.findIndex((num, _) => {
        // 左側の合計値と、全体の合計から現在の値と左側の合計値を引いた値が等しくなれば、そこがピポットとなる
        if (leftSum === totalSum - num - leftSum) {
            return true;
        }

        // 左側の合計値を更新する
        leftSum += num;
        return false;
    })
};

function findDifference(nums1: number[], nums2: number[]): number[][] {
    // num1とnum2をSetとする
    const set1 = new Set(nums1);
    const set2 = new Set(nums2);

    // set1をset2にはない値にフィルターする
    const diff1 = [...set1].filter((num) => !set2.has(num));

    // num1と同様
    const diff2 = [...set2].filter((num) => !set1.has(num));

    // 結果を返す
    return [diff1, diff2];
};

function uniqueOccurrences(arr: number[]): boolean {
    // 出現回数をkey value化する
    const occurrenceKV = arr.reduce((acc, curr) => {
        // 出現回数をカウントしてKVに保存する
        acc[curr] = (acc[curr] || 0) + 1;
        return acc;
    }, {} as { [key: number]: number });

    // 出現回数を配列化する
    const occurrences = Object.values(occurrenceKV);

    // Set化したものと同じ長さであれば重複はなくユニークなのでtrue、そうでなければfalse
    return new Set(occurrences).size === occurrences.length;
};

class RecentCounter {
    private requests: number[];

    constructor() {
        this.requests = [];
    }

    ping(t: number): number {
        // 新しいリクエストを追加する
        this.requests.push(t);

        // 3000ミリ秒より小さいリクエストを削除し、それ以上のものがあればループを抜ける
        while (this.requests[0] < t - 3000) {
            this.requests.shift();
        }

        // 現在のリクエスト数を返す
        return this.requests.length;
    }
    
}

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function reverseList(head: ListNode | null): ListNode | null {
    return reverseHelper(head, null);
};

function reverseHelper(current: ListNode | null, prev: ListNode | null) {
    // 基底ケース：現在のノードがnull（端まで到達した）なら、prevを返す
    if (current === null) {
        return prev;
    }

    // nextをtempで保存しておく
    const nextTemp = current.next;

    // current.nextをprevと入れ替える
    current.next = prev;

    // 再帰的に次の値をcurrentとして呼び出す
    return reverseHelper(nextTemp, current);
}

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function maxDepth(root: TreeNode | null): number {
    // 基底ケース：ノードがnullの場合、深さは0とする
    if (root === null) {
        return 0;
    }

    // 左右のノードを再帰で計算する
    const leftDepth = maxDepth(root.left);
    const rightDepth = maxDepth(root.right);

    // 現在のノードの深さは、子ノードの深さの最大値+1となる
    return Math.max(leftDepth, rightDepth) + 1;
};

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function leafSimilar(root1: TreeNode | null, root2: TreeNode | null): boolean {
    // 葉ノードの値の配列を取得する関数
    const getLeaves = (node: TreeNode | null, leaves: number[] = []): number[] => {
        // ノードがnullであればすぐにその時点の配列を返す
        if (!node) {
            return leaves;
        }

        // 基底ケース：左右の子ノードがどちらもnullであれば葉ノードなので、値を配列に追加する
        if (!node.left && !node.right) {
            leaves.push(node.val);
        } else {
            // 左右それぞれのノードに再帰的に関数を適用する
            getLeaves(node.left, leaves);
            getLeaves(node.right, leaves);
        }

        // 集めた配列を返す
        return leaves;
    }

    // 2つの木の葉ノードの値の配列が一致するかチェックする
    return JSON.stringify(getLeaves(root1)) === JSON.stringify(getLeaves(root2));
};

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function searchBST(root: TreeNode | null, val: number): TreeNode | null {
    // 基底ケース：現在のノードがnullであれば見つからなかったということなのでnullを返す
    if (root === null) {
        return null;
    }

    // 基底ケース：現在のノードの値がvalと等しければそのノードを返す
    if (root.val === val) {
        return root;
    }

    // 現在のノードの値がvalより大きければ、左の子ノードを探索する
    if (root.val > val) {
        return searchBST(root.left, val);
    }

    // 現在のノードの値がvalより小さければ、右の子ノードを探索する
    if (root.val < val) {
        return searchBST(root.right, val);
    }
};

function tribonacci(n: number): number {
    // 最初の3項を設定する
    let trib = [0, 1, 1];

    // nが2以下ならそのまま値を返す
    if (n <= 2) {
        return trib[n];
    }

    // n-2回、Tribonacci数を計算する
    for (let i = 3; i <= n; i++) {
        // nextを計算する
        const next = trib[0] + trib[1] + trib[2];

        // tribを1つシフトして末尾にnextを追加する
        trib = [trib[1], trib[2], next];
    }

    // 末尾の要素を返す
    return trib[2];
};

/** 
 * Forward declaration of guess API.
 * @param {number} num   your guess
 * @return 	     -1 if num is higher than the picked number
 *			      1 if num is lower than the picked number
 *               otherwise return 0
 * var guess = function(num) {}
 */


function guessNumber(n: number): number {
    // 二分探索関数を定義する
    const binarySearch = (left: number, right: number): number => {
        // leftがrightより大きければ範囲がないので-1を返す
        if (left > right) {
            return -1;
        }

        // midを計算する
        const mid = left + Math.floor((right - left) / 2);
        // midをguessする
        const res = guess(mid);

        // midが正解と等しければmidを返す
        if (res === 0) {
            return mid;
        }

        // 正解がmidより大きければ、midより上を探索する
        if (res === 1) {
            return binarySearch(mid + 1, right);
        }

        // 正解がmidより小さければ、midより下を探索する
        if (res === -1) {
            return binarySearch(left, mid - 1);
        }
    }

    // 二分探索する
    return binarySearch(1, n);
};

function singleNumber(nums: number[]): number {
    // 配列の全要素に対してXORを適用する
    return nums.reduce((acc, num) => acc ^ num, 0);
};

function countBits(n: number): number[] {
    return [...Array(n　+ 1).keys()].reduce((acc, i) => {
        // 初期値の0は既に設定されているので、そのまま返す
        if (i === 0) {
            return acc;
        }
        
        // 既に計算した1のビット数と、iの最下位ビットが1かどうかを加算して、新しい1のビットの数を求める
        acc.push(acc[i >> 1] + (i & 1));
        return acc;
    }, [0]);
};

function minCostClimbingStairs(cost: number[]): number {
    // 頂上に到達するのは0コストとする
    cost.push(0);

    // reduceで計算する
    const result = cost.reduce((acc, curr, i) => {
        // 最初の2段はそのままaccに保存する
        if (i === 0 || i === 1) {
            acc.push(curr);
        } else {
            // 1段前からか2段前からか最短ルートを計算して、currと加算し、accに保存する
            acc.push(curr + Math.min(acc[i - 1], acc[i - 2]));
        }
        return acc;
    }, [] as number[])

    // 頂上のコストを返す
    return result[result.length - 1];
};