class Solution {
    public String reverseWords(String s) {
        String[] arr = s.split("\\s+");
        for(int i = 0, j = arr.length-1; i<j; ){
            if(arr[i].equals("")){
                i++; continue;
            }
            if(arr[j].equals("")){
                j--; continue;
            }
            String temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++; j--;
        }
        StringBuilder sb = new StringBuilder();
        for(String ss: arr) {
            if(!ss.equals("")) sb.append(ss).append(" ");
        }
        return sb.toString().trim();
    }
}

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int arr[] = new int[n];
        int left[] = new int[n];
        arr[0] = left[n-1] = 1;
        for(int i=1; i<n; i++){
            arr[i] = arr[i-1]*nums[i-1];
        }
        for(int i=n-2; i>-1; i--){
            left[i] = left[i+1]*nums[i+1];
        }
        for(int i=0; i<n; i++){
            arr[i]*=left[i];
        }
        return arr;
    }
}

class Solution {
    public boolean increasingTriplet(int[] nums) {
        int small = Integer.MAX_VALUE, mid = Integer.MAX_VALUE;
        for(int n: nums){
            if(n<=small) small = n;
            else if(n<=mid) mid = n;
            else return true;
        }
        return false;
    }
}

class Solution {
    public int compress(char[] chars) {
        String s;
        StringBuilder sb = new StringBuilder();
        int count=1;
        for(int i=1; i<chars.length; i++){
            if(chars[i]==chars[i-1]){
                count++;
            }else{
                sb.append(chars[i-1]);
                if(count!=1) sb.append(count);
                count=1;
            }
        }
        
        sb.append(chars[chars.length-1]);
        if(count!=1) sb.append(count);
        s=sb.toString();
        for(int i=0; i<s.length(); i++){
            chars[i]=s.charAt(i);
        }
        return s.length();
    }
}

class Solution {
    public List<String> summaryRanges(int[] nums) {
        List<String> list = new ArrayList<>();
        if(nums.length==0) return list;
        int a=nums[0], b=nums[0];
        for(int i=1; i<nums.length; i++){
            if(nums[i]-nums[i-1]==1){
                b=nums[i];
            }else{
                if(a!=b) list.add(a+"->"+b);
                else list.add(""+a);
                a=nums[i];
                b=nums[i];
            }
        }
        if(a!=b) list.add(a+"->"+b);
        else list.add(""+a);
        return list;
    }
}

algorithm Sieve of Eratosthenes is
    input: an integer n > 1.
    output: all prime numbers from 2 through n.

    let A be an array of Boolean values, indexed by integers 2 to n,
    initially all set to true.
    
    for i = 2, 3, 4, ..., not exceeding √n do
        if A[i] is true
            for j = i2, i2+i, i2+2i, i2+3i, ..., not exceeding n do
                set A[j] := false

    return all i such that A[i] is true.

Time - O(nloglogn)

Example problem: https://leetcode.com/problems/closest-prime-numbers-in-range/description

   public static boolean isUnique(String s) {
        int[] arr = new int[128];
        for (int i=0; i<s.length(); i++) {
            int idx = s.charAt(i) - 'a';
            if (arr[idx] == 1) return false;
            arr[idx]++;
        }
        return true;
    }
    TC - O(c)
    SC - O(1)

 public static boolean isUnique2(String s) {
        int bits = 0;
        for (int i=0; i<s.length(); i++) {
            int idx = s.charAt(i) - 'a';
            if ((bits & (1 << idx)) > 0) {
                return false;
            }
            bits |= (1 << idx);
        }
        return true;
    }
    TC - O(c)
    SC - O(1)

    public static boolean f1(String s) {
        Map<Character, Integer> map = new HashMap<>();
        int oddFrequencies = 0;
        for (char ch : s.toCharArray()) {
            if (!Character.isLetter(ch)) continue;
            ch = Character.toLowerCase(ch);
            map.put(ch, map.getOrDefault(ch, 0) + 1);
            if (map.get(ch) % 2 != 0) oddFrequencies++;
            else oddFrequencies--;
        }
        return oddFrequencies <= 1;
    }
    // TC - O(n)
    // SC - O(n)

    public static boolean f2(String s) {
        int bits = 0;
        for (char ch : s.toCharArray()) {
            if (!Character.isLetter(ch)) continue;
            int k = Character.toLowerCase(ch) - 'a';
            bits ^= (1 << k);
        }
        return bits == 0 || (bits & (bits - 1)) == 0;
    }
    // TC - O(n)
    // SC - O(1)

class Solution {
    public int maxOperations(int[] nums, int k) {
        int count = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for(int n: nums){
            if(map.containsKey(n)){
                count++;
                map.put(n, map.get(n) -1);
                if(map.get(n)==0) map.remove(n);
            }else if(n<k){
                map.put(k-n, map.getOrDefault(k-n, 0) +1);
            }
        }
        return count;
    }
}