class Solution {
    int length=0, result=0;

    public int snakesAndLadders(int[][] board) {
        length = board.length;
        if(length==0) return -1;
        for(int[] arr:board){
            if(arr.length!=length) return -1;
        }

        if(length<3) return 1;

        int[] newBoard = sumBoard(board);
        boolean[] visited = new boolean[length*length];
        bfs(newBoard, visited);
        return result;
    }

    public int[] sumBoard(int[][] board) {
        int newBoard = new int[length*length];
        int cnt=0;
        for(int i=length-1; i>=0; i--){
            if(i%2==0){
                for(int j=0; j<length; j++){
                    newBoard[cnt] = board[i][j];
                }
            }else{
                for(int j=length-1; j>=0; j--){
                    newBoard[cnt] = board[i][j];
                }
            }
            cnt++;
        }
        return newBoard;
    }
}

public void bfs(int[] newBoard, boolean[] visited) {
    result = (length*length)%6>0? (length*length)/6+1 : (length*length)/6;
    int location=0, cnt=0;
    while(location<length*length){
        // 예상 시나리오가 구현될 부분 
    } 
    result = Math.min(result, cnt);
}

class Solution {
    public int snakesAndLadders(int[][] board) {
        final int n = board.length;
        final int endSquare = n * n;
        
        short[] brd = new short[endSquare + 1];
        int brdIdx = 1;
        for (int row = n - 1; row >= 0; row--) {
            for (int col = 0; col < n; col++)  brd[brdIdx++] = (short)board[row][col];
            if (--row < 0)  break;
            for (int col = n - 1; col >= 0; col--)  brd[brdIdx++] = (short)board[row][col];
        }
        
        final int bfsQueueLen = Math.min(n * n, 8 * n);
        short[] bfsQueue = new short[bfsQueueLen];
        int bfsQueueRead = 0;
        int bfsQueueWrite = 0;
        bfsQueue[bfsQueueWrite++] = 1;  // Initialize BFS queue to start at square #1

        byte[] count = new byte[endSquare + 1];
        count[1] = 1;                   // Mark the starting location as already visited.

        while (bfsQueueRead != bfsQueueWrite) {
            int currSquare = bfsQueue[bfsQueueRead++];
            bfsQueueRead %= bfsQueueLen;
            if (currSquare + 6 >= endSquare)  return count[currSquare];
            int maxOpenMove = 0;
            for (int move = 6; move >= 1; move--) {
                int nextSquare = currSquare + move;
                if (brd[nextSquare] >= 0) {
                    if ((nextSquare = brd[nextSquare]) == endSquare)  return count[currSquare];
                }
                else {
                    if (move < maxOpenMove)  // If we already moved to an open square 1 to 6
                        continue;
                    maxOpenMove = move;
                }
                if (count[nextSquare] == 0) {
                    count[nextSquare] = (byte)(count[currSquare] + 1);
                    bfsQueue[bfsQueueWrite++] = (short)nextSquare;
                    if ((bfsQueueWrite %= bfsQueueLen) == bfsQueueRead)  return 0; // Queue overflow
                }
            }
        }
        return -1;
    }
}

class Solution {
    public Node cloneGraph(Node node) {
        if(node==null) return null;
        if(node.neighbors.size()==0) return new Node(1);

        Node newNode = new Node(node.val);
        boolean[] visited = new boolean[100];
        dfs(node, newNode, visited);
        return newNode;
    }

    public void dfs(Node node, Node newNode, boolean[] visited) {
        List<Node> newNeighbors =  newNode.neighbors;
        visited[node.val] = true;
        for (Node n : node.neighbors) {
            if (!visited[n.val]) {
                newNeighbors.add(new Node(n.val));
                newNode.neighbors = newNeighbors;
                dfs(n, new Node(n.val), visited);
            }
        }
    }
}

public class Solution {
  HashMap<Integer, Node> map = new HashMap<>();

  public Node cloneGraph(Node node) {
    if (node == null) return null;
    if(node.neighbors.size()==0) return new Node(1);
    return dfs(node);
  }

  private Node dfs(Node node) {
    if (map.containsKey(node.val)) {
      return map.get(node.val);
    }

    Node cloneNode = new Node(node.val, new ArrayList<Node>());
    map.put(node.val, cloneNode);

    for (Node neighbor : node.neighbors) {
      cloneNode.neighbors.add(dfs(neighbor));
    }

    return cloneNode;
  }
}

class Solution {
    public void dfs(Node node , Node copy , Node[] visited){
        visited[copy.val] = copy;// store the current node at it's val index which will tell us that this node is now visited
        
//         now traverse for the adjacent nodes of root node
        for(Node n : node.neighbors){
//             check whether that node is visited or not
//              if it is not visited, there must be null
            if(visited[n.val] == null){
//                 so now if it not visited, create a new node
                Node newNode = new Node(n.val);
//                 add this node as the neighbor of the prev copied node
                copy.neighbors.add(newNode);
//                 make dfs call for this unvisited node to discover whether it's adjacent nodes are explored or not
                dfs(n , newNode , visited);
            }else{
//                 if that node is already visited, retrieve that node from visited array and add it as the adjacent node of prev copied node
//                 THIS IS THE POINT WHY WE USED NODE[] INSTEAD OF BOOLEAN[] ARRAY
                copy.neighbors.add(visited[n.val]);
            }
        }
        
    }
    public Node cloneGraph(Node node) {
        if(node == null) return null; // if the actual node is empty there is nothing to copy, so return null
        Node copy = new Node(node.val); // create a new node , with same value as the root node(given node)
        Node[] visited = new Node[101]; // in this question we will create an array of Node(not boolean) why ? , because i have to add all the adjacent nodes of particular vertex, whether it's visited or not, so in the Node[] initially null is stored, if that node is visited, we will store the respective node at the index, and can retrieve that easily.
        Arrays.fill(visited , null); // initially store null at all places
        dfs(node , copy , visited); // make a dfs call for traversing all the vertices of the root node
        return copy; // in the end return the copy node
    }
}

public void dfs(Node node, boolean[] visited) {
    visited[node.val] = true;
    for (Node neighbor : node.neighbors) {
        if (!visited[neighbor.val]) {
            dfs(neighbor, visited);
        }
    }
}

public void bfs(Node node, boolean[] visited) {
    Queue<Node> queue = new LinkedList<>();
    queue.offer(node);
    visited[node.val] = true;
    while (!queue.isEmpty()) {
        Node curr = queue.poll();
        for (Node neighbor : curr.neighbors) {
            if (!visited[neighbor.val]) {
                queue.offer(neighbor);
                visited[neighbor.val] = true;
            }
        }
    }
}

class WordDictionary {

    public WordDictionary() {
        
    }
    
    public void addWord(String word) {
        
    }
    
    public boolean search(String word) {
        
    }
}

/**
 * Your WordDictionary object will be instantiated and called as such:
 * WordDictionary obj = new WordDictionary();
 * obj.addWord(word);
 * boolean param_2 = obj.search(word);
 */

class WordDictionary {
    WordDictionary[] arr;
    boolean isChar;

    public WordDictionary() {
        arr = new WordDictionary[26];
        isChar = false;
    }
    
    public void addWord(String word) {
        if(root==null) root=new WordDictionary();
        WordDictionary temp=root;
        for(char c:word.toCharArray()){
            int ind=c-'a';
            if(temp.child[ind]==null) temp.child[ind]=new WordDictionary();
            temp=temp.child[ind];
        }
        temp.isLast=true;
    }
    
    public boolean search(String word) {
      if(root==null) root=new WordDictionary();
      WordDictionary temp=root;
      for(char c : word.toCharArray()){
          int idx = c-'a';
          if(temp.children[idx] == null){
             return false;
          }
          temp = temp.children[idx];
      }
      return temp.isWord == true;        
    }
}

class WordDictionary {
    boolean isLast;
    WordDictionary [] child;
    public WordDictionary() {
        this.isLast=false;
        this.child=new WordDictionary[26];
    }
    WordDictionary root;
    public void addWord(String word) {
        if(root==null) root=new WordDictionary();
        WordDictionary temp=root;
        for(char c:word.toCharArray()){
            int ind=c-'a';
            if(temp.child[ind]==null) temp.child[ind]=new WordDictionary();
            temp=temp.child[ind];
        }
        temp.isLast=true;
    }
    
    public boolean search(String word) {
        return checkWord(word,0,root);
    }
    public boolean checkWord(String word,int ind,WordDictionary temp){
        if(ind>=word.length()) return temp.isLast;
        if(temp==null) return false;
        char c=word.charAt(ind);
        if(c!='.'){
             if(temp.child[c-'a']!=null) return checkWord(word,ind+1,temp.child[c-'a']);
             else return false;
        }
        else{
            boolean b=false;
            for(int i=0;i<26;i++){
                if(temp.child[i]!=null) b= b || checkWord(word,ind+1,temp.child[i]);
            }
            return b;
        }
    }
}

class TrieNode{
  Map<Character, TrieNode> nodes = new HashMap<>();
  boolean isLast;
  
  Map<Character, TrieNode> getNodes(){
    return this.nodes;
  }
  
  boolean isLast(){
    return this.isLast;
  }
  
  void setIsLas(boolean isLast){
    this.isLast = isLast;
  }
}

class Trie {
    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }
    
    public void insert(String word) {
        TrieNode curr = root;
        for (char c : word.toCharArray()) {
            TrieNode node = curr.getChild(c);
            if (node == null) {
                node = new TrieNode();
                curr.setChild(c, node);
            }
            curr = node;
        }
        curr.setEndOfWord(true);
    }
    
    public boolean search(String word) {
        TrieNode curr = root;
        for (char c : word.toCharArray()) {
            TrieNode node = curr.getChild(c);
            if (node == null) {
                return false;
            }
            curr = node;
        }
        return curr.isEndOfWord();
    }
    
    public boolean startsWith(String prefix) {
        TrieNode curr = root;
        for (char c : prefix.toCharArray()) {
            TrieNode node = curr.getChild(c);
            if (node == null) {
                return false;
            }
            curr = node;
        }
        return true;
    }
}

class Node{
    Node children[] = new Node[26];
    boolean isWord = false;
}


class Trie {
  Node root;

    public Trie() {
        root = new Node();
    }
    
    public void insert(String word) {
        Node temp = root;
        for(char c : word.toCharArray()){
            int idx = c-'a';
            if(temp.children[idx] == null){
                temp.children[idx] = new Node();
            }
            temp = temp.children[idx];
        }
        temp.isWord = true;
    }
    
    public boolean search(String word) {
      Node temp = root;
        for(char c : word.toCharArray()){
            int idx = c-'a';
            if(temp.children[idx] == null){
               return false;
            }
            temp = temp.children[idx];
        }
        return temp.isWord == true;        
    }
    
    public boolean startsWith(String prefix) {
         Node temp = root;
        for(char c : prefix.toCharArray()){
            int idx = c-'a';
            if(temp.children[idx] == null){
                return false;
            }
            temp = temp.children[idx];
        }
        return true;
    }
}

class Solution {
    List<Double> list = new ArrayList<>();
    int valSum=0, cntSum=0;
    public List<Double> averageOfLevels(TreeNode root) {
        getAverage(root, 0);
        return list;
    }
    public void getAverage(TreeNode root, int h) {
        if(root==null) return;
        valSum+=root.val;
        cntSum++;
        getAverage(root.left, h++);
        getAverage(root.right, h++);
        list.add((double)valSum/cntSum);
    }
}

public void getAverage(TreeNode root, int h) {
    if(root==null) return;
    valSum+=root.val;
    cntSum++;
    if(root.right==null){
        list.add((double)valSum/cntSum);
        valSum=0;
        cntSum=0;
    }
    getAverage(root.left, h++);
    getAverage(root.right, h++);
}

class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> ans = new ArrayList<>();
        if(root==null){
            return ans;
        }
       Queue<TreeNode> q=new LinkedList<>();
        q.add(root);
        while(!q.isEmpty()){
            int n=q.size();
           double avg=0l;
            for(int i=0;i<n;i++){
                 TreeNode curr=q.poll();
                avg=avg+(double)curr.val;
                if(curr.left!=null){q.add(curr.left);}
                if(curr.right!=null){q.add(curr.right);}
            }
            avg=avg/n;
            ans.add(avg);
        }
       return ans; 
    }
}

class Solution {
    int h=0;
    List<Integer> list = new ArrayList<>();
    public hList<Integer> rightSideView(TreeNode root) {
        deepth(root);
        getRight(root);
        if(h==list.size()) return list;
        else{
            
        }
    }

    public void deepth(TreeNode root){
        if(root==null) return; 
        deepth(root.left);
        h++;
        deepth(root.right);
    }

    public void getRight(TreeNode root){
        if(root==null) return; 
        list.add(root.val);
        deepth(root.right);
    }
}

class Solution {
    int h=0;
    List<Integer> list = new ArrayList<>();
    public List<Integer> rightSideView(TreeNode root) {
        if(root==null) return null;
        if(h==list.size()) list.add(root.val);

        rightSideView(root.right);
        h++;
        rightSideView(root.left);

        return list;
    }
}

public class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        rightView(root, result, 0);
        return result;
    }
    
    public void rightView(TreeNode curr, List<Integer> result, int currDepth){
        if(curr == null){
            return;
        }
        if(currDepth == result.size()){
            result.add(curr.val);
        }
        
        rightView(curr.right, result, currDepth + 1);
        rightView(curr.left, result, currDepth + 1);
    }
}

public class Solution {
    public List<Integer> leftSideView(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        rightView(root, result, 0);
        return result;
    }
    
    public void leftView(TreeNode curr, List<Integer> result, int currDepth){
        if(curr == null){
            return;
        }
        if(currDepth == result.size()){
            result.add(curr.val);
        }

        leftView(curr.left, result, currDepth + 1);
        leftView(curr.right, result, currDepth + 1);
    }
}

class Solution {
    List<Integer> list = new ArrayList<>();
    public int kthSmallest(TreeNode root, int k) {
        if(root==null){
            Collections.sort(list);
            if(list.size()<k) return 0;
            else return list.get(k-1);
        } 
        list.add(root.val);
        kthSmallest(root.left, k);
        kthSmallest(root.right, k);

        Collections.sort(list);
        if(list.size()<k) return 0;
        else return list.get(k-1);
    }
}

class Solution {
    List<Integer> list = new ArrayList<>();
    public int kthSmallest(TreeNode root, int k) {
        if(root==null){
            return getAnswer(list, k);  
        } 
        list.add(root.val);
        kthSmallest(root.left, k);
        kthSmallest(root.right, k);
        return getAnswer(list, k);        
    }

    public int getAnswer(List<Integer> list, int k) {
        Collections.sort(list);
        if(list.size()<k) return 0;
        else return list.get(k-1);

    }
}

class Solution {
    List<Integer> list=new ArrayList<>();
    public int kthSmallest(TreeNode root, int k) {
        if(root==null)return 0;
        help(root,k);
        return list.get(k-1);
    }
    public void help(TreeNode root,int k)
    {
        if(root==null)return;
        help(root.left,k);
        list.add(root.val);
        if(list.size()==k)return;
        help(root.right,k);
    }
}

public class Solution {
    int result;
    int count;

    public int kthSmallest(TreeNode root, int k) {
        count = 0;
        inOrderTraversal(root, k);
        return result;
    }

    private void inOrderTraversal(TreeNode node, int k) {
        if (node == null) return;
        
        inOrderTraversal(node.left, k);
        count++;
        
        if (count == k) {
            result = node.val;
            return;
        }
        
        inOrderTraversal(node.right, k);
    }
}

class Solution {
    int left=0, right=0;
    public int getMinimumDifference(TreeNode root) {
        TreeNode lroot = root;
        TreeNode rroot = root;
        while(lroot.left!=null){
            lroot = lroot.left;
            left++;
        }
        while(rroot.right!=null){
            rroot = rroot.right;
            right++;
        }
        return Math.abs(left-right);
    }
}

class Solution {
  int min=10000, prev=0;
  public int getMinimumDifference(TreeNode root) {
    if(root==null) return min;
    getMinimumDifference(root.left);
    if(prev!=0) min=Math.min(min, Math.abs(root.val-prev));
    prev=root.val;
    getMinimumDifference(root.right);

    return min;
  }
}

class Solution {
  int prev = -100000, min = 100000;
  public int getMinimumDifference(TreeNode root) {
    if(root==null) return min;
    getMinimumDifference(root.left);
    min=Math.min(min, root.val-prev);
    prev=root.val;
    getMinimumDifference(root.right);
    return min;
  }
}

class Solution {
    int min = Integer.MAX_VALUE;
    TreeNode prev = null;
    
    public int getMinimumDifference(TreeNode root) {
        inOrderTraversal(root);
        return min;
    }

    private void inOrderTraversal(TreeNode node) {
        if (node == null) {
            return;
        }

        inOrderTraversal(node.left);

        if (prev != null) {
            min = Math.min(min, Math.abs(node.val - prev.val));
        }
        prev = node;

        inOrderTraversal(node.right);
    }
}

class Solution {
    public int search(int[] nums, int target) {
        List<Integer> list = new ArrayList<>();
        for(int i:nums){
            list.add(i);
        }
        int index = list.indexOf(target);
        if(index==-1) return -1;
        else return index;
    }
}

class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] >= nums[left]) {
                if (target >= nums[left] && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else {
                if (target <= nums[right] && target > nums[mid]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return -1;
    }
}

class Solution {
  public int search(int[] nums, int target) {
    int n = nums.length ;
    for( int i = 0 ; i< n ; i++){
      if( nums[i]==target ){
        return i ;
      }
    }
    return -1;
  }
}

class Solution {
    public int findMin(int[] nums) {
        for(int i=0; i<nums.length-1; i++){
            if(nums[i]>nums[i+1]) return nums[i+1];
        }
        return nums[0];
    }
}

class Solution {
  public int findMin(int[] nums) {
    int n = nums.length;
    if(n==1) return nums[0];

    int left = 0, right = n-1;
    if(nums[right]>nums[0]) return nums[0];

    while(left<right){
      int mid = left + (right-left)/2;
      if(nums[mid]>nums[mid+1]) return nums[mid+1];
      if(nums[mid-1]>nums[mid]) return nums[mid];
      if(nums[mid]>nums[0]){
        left = mid+1;
      } else {
        right = mid-1;
      }
    }
    return nums[left];
  }
}

class Solution {
    public int findMin(int[] nums) {
        int left = 0;
        int right = nums.length - 1;

        while (left < right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] > nums[right]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return nums[left];
    }
}

class Solution {
    public int findPeakElement(int[] nums) {
        List<Integer> list = new ArrayList<>();
        for(int i:nums){
            list.add(i);
        }
        Arrays.sort(nums);
        int answer = list.indexOf(nums[nums.length-1]);
        return answer;
    }
}

class Solution {
   public int findPeakElement(int[] nums) {
      int left=0, right=nums.length-1;
      int middle=(nums[left]+nums[right])/2;
      while(left<right){
         if(nums[middle-1]<nums[middle] && nums[middle+1]<nums[middle]) return middle;
         if(nums[middle-1]<nums[middle]) left=middle+1;
         else right=middle-1;
      }
      return left; 
   }
}

class Solution {
    public int findPeakElement(int[] nums) {
        int n = nums.length;
        if(n == 1 || nums[0] > nums[1]) return 0;
        if(nums[n - 1] > nums[n - 2]) return n - 1;
        int l = 0;
        int r = n - 1;
        while(l <= r)
        {
            int m = (l + r)/2;
            int minus = m == 0 ? Integer.MIN_VALUE : nums[m-1];
            int plusUltra = m == n - 1 ? Integer.MIN_VALUE : nums[m+1];
            if(minus < nums[m] && plusUltra < nums[m]) return m;
            if(minus < nums[m]) l = m + 1;
            else r = m - 1;
        }
        return l;
    }
}

class Solution {
    public ListNode sortList(ListNode head) {
        if(head==null) return head;
        
        List<Integer> list = new ArrayList<>();
        while(head!=null){
            list.add(head.val);
            head = head.next;
        }
        Collections.sort(list);
        Collections.reverse(list);

        ListNode answer = new ListNode();
        for(int i=0; i<list.size(); i++){
            if(i==0) answer = new ListNode(list.get(i));
            else answer = new ListNode(list.get(i), answer);
        }
        return answer;
    }
}

public ListNode sortList(ListNode head) {
  ListNode dummy = new ListNode(0);
  dummy.next = head;

  ListNode [] sublists = new ListNode[2];
  ListNode [] sublists_tail = new ListNode[2];

  // Grab sublists of size 1, then 2, then 4, etc, until fully merged
  for (int steps = 1;; steps *= 2) {
    // Record the progress of the current pass into a single semi sorted list by updating
    // the next of the previous node (or the dummy on the first loop)
    ListNode prev = dummy;

    // Keep track of how much is left to process on this pass of the list
    ListNode remaining = prev.next;

    int num_loops = 0;
    for (; null != remaining; ++num_loops) {
      // Split 2 sublists of steps length from the front
      for (int i = 0; i < 2; ++i) {
        sublists[i] = remaining;
        sublists_tail[i] = null;
        for (int j = 0; null != remaining && j < steps; ++j) {
          sublists_tail[i] = remaining;
          remaining = remaining.next;
        }
        // Ensure the subslist (if one was made) is terminated
        if (null != sublists_tail[i]) {
          sublists_tail[i].next = null;
        }
      }

      // We have two sublists of (upto) length step that are sorted, merge them onto the end into a single list of (upto) step * 2
      while (null != sublists[0] && null != sublists[1]) {
        if (null == sublists[1] || sublists[0].val <= sublists[1].val) {
          prev.next = sublists[0];
          sublists[0] = sublists[0].next;
        } else {
          prev.next = sublists[1];
          sublists[1] = sublists[1].next;
        }
        prev = prev.next;
      }   

      // One list has been finished, attach what ever is left of the other to the end
      if (null != sublists[0]) {
        prev.next = sublists[0];
        prev = sublists_tail[0];
      } else {
        prev.next = sublists[1];
        prev = sublists_tail[1];
      }
    }

    // If the entire list was full processed in a single loop, it means we've completely sorted the list and are done
    if (1 >= num_loops) {
      return dummy.next;
    }
  }
}

class Solution {
    public ListNode sortList(ListNode head) {
        int count = 0;
        ListNode temp = head;
        while(temp!=null){
            count++;
            temp = temp.next;
        }
        int[] arr = new int[count];
        temp = head;
        count = 0;
        while(temp!=null){
            arr[count++] = temp.val;
            temp = temp.next;
        }
        Arrays.sort(arr);
        temp = head;
        count = 0;
        while(temp!=null){
            temp.val = arr[count++];
            temp = temp.next;
        }
        return head;
    }
}

class Solution {
  public boolean isAnagram(String s, String t) {
    Map<Character, Integer> s_map = makeMap(s);
    Map<Character, Integer> t_map = makeMap(t);
    
    if(s.length()!=t.length()) return false;

    for(int i=0; i<t.length(); i++){
      char c = t.charAt(i);
      if(!s_map.containsKey(c)) return false;
      if(s_map.get(c)!=t_map.get(c)) return false;
    }
    return true;
  }

  public Map<Character, Integer> makeMap(String str){
    Map<Character, Integer> map = new HashMap<>();
    for(int i=0; i<str.length(); i++){
      char c = str.charAt(i);
      if(map.containsKey(c)) map.put(c, map.get(c)+1);
      else map.put(c, 1);
    }
    return map;
  }
}

// s_map
{a=1913, b=2003, c=2000, d=1916, e=1978, f=1880, g=1949, h=1943, i=1949, j=1891, k=1923, 
        l=1922, m=1936, n=1978, o=1869, p=1874, q=1875, r=1985, s=1897, t=1838, u=1879, 
        v=1905, w=1940, x=1942, y=1915, z=1900}
// t_map        
{a=1913, b=2003, c=2000, d=1916, e=1978, f=1880, g=1949, h=1943, i=1949, j=1891, k=1923, 
        l=1922, m=1936, n=1978, o=1869, p=1874, q=1875, r=1985, s=1897, t=1838, u=1879, 
        v=1905, w=1940, x=1942, y=1915, z=1900}
        
50000
50000
// if(s.length()!=t.length()) return false;        
false

class Solution {
    public boolean isAnagram(String s, String t) {
        char[] sChars = s.toCharArray();
        char[] tChars = t.toCharArray();
        Arrays.sort(sChars);
        Arrays.sort(tChars);
        return Arrays.equals(sChars, tChars);
    }
}

class Solution {
    public boolean isAnagram(String s, String t) {
        Map<Character, Integer> count = new HashMap<>();
        
        for (char x : s.toCharArray()) {
            count.put(x, count.getOrDefault(x, 0) + 1);
        }
        
        for (char x : t.toCharArray()) {
            count.put(x, count.getOrDefault(x, 0) - 1);
        }
        
        for (int val : count.values()) {
            if (val != 0) {
                return false;
            }
        }
        
        return true;
    }
}

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        Map<Character, Integer> ransomNote_map = makeMap(ransomNote);
        Map<Character, Integer> magazine_map = makeMap(magazine);

        for(int i=0; i<ransomNote.length(); i++){
            char c = ransomNote.charAt(i);
            if(!magazine_map.containsKey(c)) return false;
            if(ransomNote_map.getOrDefault(c,0)>magazine_map.getOrDefault(c,0)) return false;
        }
        return true;
    }

    public Map<Character, Integer> makeMap(String str){
        Map<Character, Integer> map = new HashMap<>();
        for(int i=0; i<str.length(); i++){
            char c = str.charAt(i);
            if(map.containsKey(c)) map.put(c, map.get(c)+1);
            else map.put(c, 1);
        }
        return map;
    }
}

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        int[] charCounts = new int[26]; // Assuming lowercase English letters
        
        for (char c : magazine.toCharArray()) {
            charCounts[c - 'a']++;
        }

        for (char c : ransomNote.toCharArray()) {
            if ( !(charCounts[c - 'a'] > 0 ) ) {
                return false;
            } 
                charCounts[c - 'a']--;
        }
        
        return true;
    }
}

class Solution {
  public boolean containsNearbyDuplicate(int[] nums, int k) {
    Map<Integer, Integer> map = new HashMap<>();
    for(int i=0; i<nums.length; i++){
      if(map.containsKey(nums[i])){
        int a = map.get(nums[i]);
        if(i-a<=k) return true;
      }
      map.put(nums[i], i);
    }
    return false;
  }
}

public boolean containsNearbyDuplicate(int[] nums, int k) {
  Set<Integer> set = new HashSet<Integer>();
  for(int i = 0; i < nums.length; i++){
      if(i > k) set.remove(nums[i-k-1]);
      if(!set.add(nums[i])) return true;
  }
  return false;
}

class Solution {
  public int[] twoSum(int[] nums, int target) {
    List<Integer> list = new ArrayList<>();
    for(int i:nums){
      list.add(i);
    }
    int i=0, a=0, b=0;
    for(i=0; i<nums.length; i++){
      a = target-nums[i];
      b = list.lastIndexOf(a);
      if(a>0 && b!=-1 && b!=i){
        break;
      }
    }
    return new int[]{i, b};
  }
}

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> numMap = new HashMap<>();
        int n = nums.length;

        for (int i = 0; i < n; i++) {
            int complement = target - nums[i];
            if (numMap.containsKey(complement)) {
                return new int[]{numMap.get(complement), i};
            }
            numMap.put(nums[i], i);
        }

        return new int[]{}; // No solution found
    }
}

class Solution {
  public int evalRPN(String[] tokens) {
    Stack<Integer> stack = new Stack<>();
    int next;
    for(String s:tokens){
      if(Character.isDigit(s.charAt(0))){
        stack.push(Integer.parseInt(s));
      }
      else{
        int b = stack.pop();
        int a = stack.pop();

        if("+".equals(s)) stack.push(a+b);
        else if("-".equals(s)) stack.push(a-b);
        else if("*".equals(s)) stack.push(a*b);
        else stack.push(a/b);
      }
      System.out.println(stack);
    }
    return stack.pop();
  }
}

if("+".equals(s) || "-".equals(s) || "*".equals(s) || "/".equals(s))

class Solution {
  public int evalRPN(String[] tokens) {
    Stack<Integer> stack = new Stack<>();
    Set<String> ops = Set.of("+", "-", "*", "/");

    for (String s : tokens) {
      if (ops.contains(s)) {
        int a = stack.pop();
        int b = stack.pop();
        int c = 0;

        switch(s) {
          case "+" -> {c = b + a;}
          case "-" -> {c = b - a;}
          case "*" -> {c = b * a;}
          case "/" -> {c = b / a;}
        }
        stack.push(c);
      }
      else stack.push(Integer.parseInt(s));
    }
    return stack.peek();
  }
}

// TC: O(n), SC: O(n)

class MinStack {
  LinkedList<Integer> list;

  public MinStack() {
    list = new LinkedList<>();
  }

  public void push(int val) {
    list.push(val);
  }

  public void pop() {
    list.removeFirst();
  }

  public int top() {
    return list.peekFirst();
  }

  public int getMin() {
    LinkedList<Integer> sortedList =  new LinkedList<>(list);
    Collections.sort(sortedList);
    return sortedList.peekFirst();
  }
}

class MinStack {
    LinkedList<TplusMin> stack;
    private class TplusMin {
        int val;
        int min;
        public TplusMin(int val, int min) {
            this.val = val;
            this.min = min;
        }
    }

    public MinStack() {
        stack = new LinkedList<>();
    }
    
    public void push(int val) {
        int newMin;
        if (stack.size() == 0){
            newMin = val;
        }
        else {
            int currentMin = stack.getFirst().min;
            newMin = val < currentMin ? val : currentMin;
        }
        stack.addFirst(new TplusMin(val, newMin));
    }
    
    public void pop() {
        stack.removeFirst();
    }
    
    public int top() {
        return stack.peekFirst().val;
    }
    
    public int getMin() {
        return stack.peekFirst().min;
    }
}

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int answer = 1;
        for(int i=0; i<s.length()-1; i++){
            int j=i+1;
            while(j<s.length()){
                j++;
                String substring = s.substring(i,j);
                if(substring.indexOf(""+s.charAt(j))==-1){
                    answer = Math.max(answer, j-i);
                }
                else break;                
            }
        }
        return answer;
    }
}