Longest Continuous Ones of a String contains 0 or 1 - inch worm algorithm

Given a string consisted of only 0 or 1, and a number N.

We have N times to flip 0 to 1 in array. Find the longest continuous 1 after we flipped the N zero elements. Rotation is allowed.

For example, 100100111000, n=2, the best flip is 100111111000, return 6

10001101101, n=2, the best flip is 10001111111, return 8(rotation is allowed)

The following algorithm is more like a inch worm walking on a line, it tries to go forward as it can, then shrink from the tail, then move forward again.

/**
     * we first concatenate string to itself
     *
     * then use a sliding window, keep track of number of 0s in the window
     * grow the right side of window if not exceed max 0s allowed
     * otherwise shrink the left side to reduce the 0s
     *
     * the algorithm stops when left side reach the length of original string
     *
     */
    public static int maxContinuous1sWithRotation(String s, int maxFlips){
        int p1=0, p2=0, len = s.length(), num0=0, max=0;
        while(p1<len && p2-p1<len){
            if(s.charAt(p2%len) == '0'){
                num0++;
            }
           
            /*
             * if num0 reaches maxFlips+1
             * we need to shrink the sliding window from left
             * until we reaches a 0 and reduce the counter
             */
            if(num0 > maxFlips){               
                while(p1<len && s.charAt(p1)=='1')
                    p1++;
                p1++; num0--;
            }
           
            /*
             * we keep on growing the sliding window
             * to the right and update the max
             */
            p2++;
            max = Math.max(max, p2-p1);       
        }
        return max;
    }

all permutations of list of characters

Given a list of unique characters, generate or print out all permutations of characters.
For example:
input: [a, b, c]
output:
[a, b, c]
[b, a, c]
[c, b, a]
[a, c, b]
[b, c, a]
[c, a, b]

One of the permutation algorithm is done by swapping,
We have a list of permutations, which initially contains the input characters only.
Then we have two loops, outer loop (i) goes through index 0 to len-2, inner loop (j) goes from index i+1 to len-1, and for each current permutation, we generate one new by swap characters at i and j.


public static void permuIteratively(char[] chars){
        assert chars!=null && chars.length>0;
       
        List<char[]> result = new ArrayList<char[]>();
        result.add(chars);
        int len = chars.length;
       
        /*
         * the algorithm is doing swapping with two loops
         * i: 0..len-2
         *   j: i+1..len-1
         *    for each string in the result list
         *     swap characters at i and j
         *     add swapping result string to the result
         *    
         * since we can't change the list which iterating through list
         * so we have to make a temp copy of the result and add swapping result
         * into temp list   
         *
         */
       
        for(int i=0; i<len-1; i++){
            //make a copy of result
            List<char[]> temp = new ArrayList<char[]>(result);
            for(int j=i+1;j<len;j++){   
                //loop through result and swap i and j
                for(char[] item : result){
                    char[] copy = Arrays.copyOf(item, item.length);
                    char tempC = copy[i];
                    copy[i] = copy[j];
                    copy[j] = tempC;
                    temp.add(copy);
                }           
            }
            result = temp;
        }
       
        for(char[] i : result){
            System.out.println(Arrays.toString(i));
        }
    }


Once we find a way do it in iteratively, it is not difficutlt to switch to recursive way .

public static void permu(char[] chars){
        List<char[]> l = new ArrayList<char[]>();
        l.add(chars);
        permuRec(chars, 0, l);
    }
    public static void permuRec(char[] chars, int index, List<char[]> current){
        /*
         * termination condition
         */
        if(index==chars.length-1){
            for(char[] i : current){
                System.out.println(Arrays.toString(i));
            }
            return;
        }
       
        //make a copy of result
        List<char[]> temp = new ArrayList<char[]>(current);
        //then we grow the result by swapping
        for(int j=index+1;j<chars.length;j++){
            for(char[] item : current){
                char[] copy = Arrays.copyOf(item, item.length);
                char tempC = copy[index];
                copy[index] = copy[j];
                copy[j] = tempC;
                temp.add(copy);
            }
        }
        //continue on next index
        permuRec(chars, index+1, temp);
    }
   

Another way to do it is to by reduction. Basically we divide and conquer,  find the permutations for substring start at i+1 first, then insert the character at i into all positions for each permutation from the subpromblem.

/**
     * we solve this by reduction, for string s,
     * first find the permutation of its substring from i+1
     * then for each permutation, insert the character at i
     * into all positions
     *
     * @param chars
     */
    public static void permutationByDP(char[] chars){
        System.out.println(permutationByReduRec(chars, 0));
    }
   
    public static List<List<Character>> permutationByReduRec(char[] chars, int index){
        /*
         * permutations are represented by list of characters
         */
        List<List<Character>> result = new ArrayList<List<Character>>();
        if(index == chars.length-1){
            /**
             * base case is the string only has one character
             */
            List<Character> list = new ArrayList<Character>();
            list.add(chars[index]);           
            result.add(list);
        }
        else{
            /*
             * we build the permutation by its substring index+1 first
             */
            List<List<Character>> list = permutationByReduRec(chars, index+1);
            char insert = chars[index];
            for(List<Character> item : list){
                /*
                 * then we insert char at index to all possible positions in the item
                 */
                for(int i=0; i<=item.size(); i++){
                    List<Character> copy = new ArrayList<Character>(item);
                    copy.add(i, insert);
                    result.add(copy);
                }

            }
        }
        return result;       
    }
   

find duplicate elements k indices away in matrix

There are two problems which are quite similar to each other.

Given an array of integer, find duplicates which are within k indices away.  See this link for reference:
http://www.geeksforgeeks.org/check-given-array-contains-duplicate-elements-within-k-distance/

Given a 2D array of integer, find duplicates which are within k indices away.

Both can be solved by using a sliding window of k indicies, maintain a hash storing the elements seen so far then check if the next element is in the hash, if not, remove the element at the start of sliding window and continue.

//for list of integers

public static boolean hasKDistanceDuplicate(int[] array, int k){

Set<Integer> store = new HashSet<Integer>();

for(int i=0, j=0; i<array.length; i++){

//maintain a sliding window of k size

while(j<array.length && j-i<=k){

if(store.contains(array[j])){

return true;

}else{

store.add(array[j]);

j++;

}

}

if(j<array.length)

store.remove(array[i]);

}

return false;

}

//for 2D matrix of integers

public static boolean determineKIndices(int[][] matrix, int k){

Map<Integer, Set<Pos>> store = new HashMap<Integer, Set<Pos>>();

for(int row=0; row<matrix.length; row++){

for(int col=0; col<matrix[0].length; col++){

int val = matrix[row][col];

if(store.containsKey(val)){

Set<Pos> set = store.get(val);

for(Pos p: set){

if(Math.abs(p.getRow() - row) + Math.abs(p.getCol()-col) <=k ){

return true;

}

      if(row - p.getRow() >k)
        set.remove(p);

}

set.add(new Pos(row, col));

}else{

Set<Pos> set = new HashSet<Pos>();

set.add(new Pos(row, col));

store.put(val, set);

}

}

}

return false;

}