Java solution very fast O(n^2) Time complexity - n is the length of input string array


  • 0
    Q
    public class Solution {
      public int findMaxForm(String[] strs, int m, int n) {
            Obj objs[] = new Obj[strs.length];
    
            for (int i = 0; i < strs.length; i++) {
                int ones = 0;
                int zeros = 0;
                for (int j = 0; j < strs[i].length(); j++) {
                    char charAt = strs[i].charAt(j);
                    if (charAt == '0') zeros++;
                    if (charAt == '1') ones++;
                }
                Obj obj = new Obj();
                obj.numOfOne = ones;
                obj.numOfZero = zeros;
                obj.length = strs[i].length();
                objs[i] = obj;
            }
            Arrays.sort(objs, new Comparator<Obj>() {
                @Override
                public int compare(Obj o1, Obj o2) {
                    int temp = o1.length - o2.length;
                    if (temp == 0) temp = Math.abs(o1.numOfOne - o1.numOfZero) - Math.abs(o2.numOfOne - o2.numOfZero);
                    if (temp == 0) temp = o1.numOfOne - o2.numOfOne;
                    return temp;
                }
            });
            for (int i = 0; i < strs.length; i++) {
                helper(objs, m, n, 0, i);
            }
            return max;
        }
    
    
        static class Obj {
            public int numOfZero;
            public int numOfOne;
            public int length;
    
    
        }
        int max = 0;
       public  void helper(Obj[] objs, int leftZeros, int leftOnes, int count, int index) {
            if (index==objs.length)return;
            count++;
            int x = leftOnes - objs[index].numOfOne;
            int y = leftZeros - objs[index].numOfZero;
          if (x < 0 || y < 0) {
                count--;
                helper(objs, leftZeros, leftOnes, count, index + 1);
            } else {
                max = Math.max(max, count);
                helper(objs, y, x, count, index + 1);
            }
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.