class Solution {
    public int maxScore(String s) {
        int zeros = 0, ones = 0, max = Integer.MIN_VALUE;
      for(int i=0;i<s.length();i++) {
        if(s.charAt(i) == '0') zeros++; else ones++;
        if(i != s.length()-1) max = Math.max(zeros - ones, max);
      }
      return max + ones;
    }
}

select d.name as 'Department', e.name as 'Employee',
e.salary as 'Salary' from employee e 
join department d on e.departmentid = d.id
where (e.departmentid, e.salary) in
(select departmentid, max(salary)
 from employee group by departmentid);

class Solution {
    public int numberOfArrays(int[] differences, int lower, int upper) {
        long min = 0, max = 0, curr = 0;
        
        for(int d: differences){
            curr += d;
            min = Math.min(min, curr);
            max = Math.max(max, curr);
        }
        
        long rangeDifference = (upper-lower) - (max-min) + 1;
        return (int)Math.max(rangeDifference, 0);
    }
}

class Solution {
    public boolean detectCapitalUse(String word) {
        int lower=0;
        for(char ch: word.toCharArray()){
            if(ch>=97 && ch<=122)
                lower++;
        }
        
        return word.charAt(0)<=90 ? lower == word.length()-1 || lower == 0 : lower == word.length();
    }
}

class Solution {
    public int minOperations(int n) {
        return n*n/4;
    }
}

select distinct l1.num as ConsecutiveNums from
logs l1, logs l2, logs l3 
where l1.num=l2.num && l2.num=l3.num && l1.id+1=l2.id && l2.id+1=l3.id;

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int start = 1, end = n, middle=(n+1)/2;
        while(start<=end){
            middle = end + (start - end) / 2;
            if(isBadVersion(middle))
                end=middle-1;
            else
                start=middle+1;
        }
        
        return start;
    }
}

class Solution {
    public int countElements(int[] nums) {
        int min=Integer.MAX_VALUE, max=Integer.MIN_VALUE, mins=1, maxs=1;
        for(int n: nums){
            if(n == max){
                maxs++;
            }
            if(n == min){
                mins++;
            }
            if(n>max){
                max = n;
                maxs = 1;
            }
            if(n < min){
                min = n;
                mins = 1;
            }
        }
        
        return Math.max(nums.length-mins-maxs, 0);
    }
}

class Solution {
    public void rotate(int[] nums, int k) {
        k %= nums.length;
        reverse(nums, 0, nums.length-1);
        reverse(nums, 0, k-1);
        reverse(nums, k, nums.length-1);
    }
    
    public void reverse(int[] nums, int start, int end){
        while(start<end){
            int temp = nums[start];
            nums[start]=nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
    }
}

class ParkingSystem {
    int big, medium, small;

    public ParkingSystem(int big, int medium, int small) {
        this.big=big;
        this.medium=medium;
        this.small=small;
    }
    
    public boolean addCar(int carType) {
        int type = carType%3;
        if(type==1)
            return --big>=0;
        else if(type == 2)
            return --medium >= 0;
        else
            return --small >= 0;
    }
}

public int countPoints(String rings) {
        int n = rings.length()/2;
        int arr1[] = new int[10];
        int arr2[] = new int[10];
        int arr3[] = new int[10];
        int count = 0;
        
        for(int i=0; i<n; i++){
            if(rings.charAt(2*i) == 'R')
                arr1[rings.charAt(2*i+1)-'0']++;
            if(rings.charAt(2*i) == 'G')
                arr2[rings.charAt(2*i+1)-'0']++;
            if(rings.charAt(2*i) == 'B')
                arr3[rings.charAt(2*i+1)-'0']++;
        }
        
        for(int i=0; i<10; i++){
            if(arr1[i]*arr2[i]*arr3[i] != 0)
                count++;
        }
        
        return count;
    }

class SubrectangleQueries {
    int height, width;
    int[][] rect;

    public SubrectangleQueries(int[][] rectangle) {
        this.rect = rectangle;
    }
    
    public void updateSubrectangle(int row1, int col1, int row2, int col2, int newValue) {
        for(int i=row1; i<=row2; i++){
            for(int j=col1; j<=col2; j++){
                rect[i][j] = newValue;
            }
        }
    }
    
    public int getValue(int row, int col) {
        return rect[row][col];
    }
}

class Solution {
    public int minimumSum(int num) {
        int[] arr = new int[4];
        
        for(int i=0; i<4; i++){
            arr[i] = num%10;
            num/=10;
        }
        
        Arrays.sort(arr);
        
        return 10*(arr[0]+arr[1])+arr[2]+arr[3];
    }
}

class Solution {
    public List<List<Integer>> groupThePeople(int[] gr) {
        Map<Integer, List<Integer>> map = new HashMap();
        List<List<Integer>> ans = new ArrayList();
        
        for(int i=0; i<gr.length; i++){
            int curr = gr[i];
            List<Integer> temp = new ArrayList();
            if(map.containsKey(curr)) temp = map.get(curr);
            temp.add(i);
            map.put(curr, temp);
            if(temp.size() == curr){
                ans.add(temp);
                map.remove(curr);
            }
        }
        
        return ans;
    }
}

class Solution {
    public int numberOfBeams(String[] bank) {
        int rows = bank.length, cols = bank[0].length();
        int total=0, counter = 0;
        List<Integer> nums = new ArrayList();
        for(int i = 0; i<rows; i++){
            int temp = 0;
            for(int j=0; j<cols; j++){
                if(bank[i].charAt(j) == '1') temp++;
            }
            
            if(temp != 0) nums.add(temp);
        }
        
        for(int i=1; i<nums.size(); i++){
            total += nums.get(i-1) * nums.get(i);
        }
        
        return total;
    }
}

class Solution {
    public char findTheDifference(String s, String t) {
        int n = s.length();
        char ch=t.charAt(n);
        for(int i=0; i<n; i++){
            ch ^= s.charAt(i);
            ch ^= t.charAt(i);
        }
        
        return ch;
    }
}

class Solution {
    public int[] rearrangeArray(int[] nums) {
        int pos[] = new int[nums.length/2], neg[] = new int[nums.length/2], count1=0, count2=0;
        
        for(int n: nums){
            if(n>0) pos[count1++]=n;
            if(n<0) neg[count2++]=n;
        }
        
        for(int i=0; i<nums.length/2; i++){
            nums[i*2]=pos[i];
            nums[2*i+1]=neg[i];
        }
        
        return nums;
    }
}

class Solution {
    public String makeGood(String s) {
        Stack<Character> stack = new Stack();
        for(char ch: s.toCharArray()){
            if(!stack.isEmpty() && Math.abs(stack.peek()-ch) == 32)
                stack.pop();
            else
                stack.push(ch);
        }
        
        char temp[] = new char[stack.size()];
        int n = stack.size()-1;
        while(!stack.isEmpty()){
            temp[n--] = stack.pop();
        }
        
        return new String(temp);
    }
}

class MyQueue {
    Stack<Integer> stack = new Stack();
    Stack<Integer> temp = new Stack();
    
    public MyQueue() {}
    
    public void push(int x) {
        while(!stack.isEmpty())
            temp.push(stack.pop());
        
        stack.push(x);
        while(!temp.isEmpty())
            stack.push(temp.pop());
    }
    
    public int pop() {
        return stack.pop();
    }
    
    public int peek() {
        return stack.peek();
    }
    
    public boolean empty() {
        return stack.isEmpty();
    }
}

class MinStack {
    Stack<Integer> stack = new Stack();
    int min = Integer.MAX_VALUE;
    
    public MinStack() {}
    
    public void push(int val) {
        if(val<=min){
            stack.push(min);
            min=val;
        }
        stack.push(val);
    }
    
    public void pop() {
        if(stack.pop() == min) min = stack.pop();
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int getMin() {
        return min;
    }
}