optimized code for longestsubsequence for a String

String find_lcss(String s1, String s2) {
        if (s1 == null || s2 == null) {
            return "";
        }
        int[][] table = new int[s1.length()][s2.length()];
        int maxLen = 0;
        int end_index = 0;

        for (int i = 0; i < s1.length(); i++) {
            for (int j = 0; j < s2.length(); j++) {
                if (s1.charAt(i) != s2.charAt(j)) {
                    table[i][j] = 0;
                } else {
                    if (i == 0 || j == 0) {
                        table[i][j] = 1;
                    } else {
                        table[i][j] = table[i - 1][j - 1] + 1;
                    }
                }
                if (maxLen < table[i][j]) {
                    maxLen = table[i][j];
                    end_index = i;
                }
            }
        }
     
        StringBuilder res = new StringBuilder();
        for (int i = end_index + 1 - maxLen; i <= end_index ; i++) {
            res.append(s1.charAt(i));
        }
        return res.toString();
//System.out.println(end_index);
    }

WAP to find longest repeating subsequence

String longestSubstr(String str, String toCompare) {
        if (str == null || toCompare == null) {
            return null;
        }
        int[][] compareTable = new int[str.length()][toCompare.length()];
        int maxLen = 0;
        StringBuilder res = new StringBuilder();
        int m = 0, n = 0;
        for (; m < str.length(); m++) {
            for (; n < toCompare.length(); n++) {
                compareTable[m][n] = (str.charAt(m) != toCompare.charAt(n)) ? 0
                        : (((m == 0) || (n == 0)) ? 1
                        : compareTable[m - 1][n - 1] + 1);
                maxLen = (compareTable[m][n] > maxLen) ? compareTable[m][n]
                        : maxLen;
            }
        }
        for (int i = m + 1 - maxLen; i < m; i++) {
            res.append(str.charAt(i));
        }
        return res.toString();
    }

WAP for longest repeating subsequence

// return the longest repeated string in s

    public static String lrs(String s) {

        // form the N suffixes

        int N  = s.length();

        String[] suffixes = new String[N];

        for (int i = 0; i < N; i++) {

            suffixes[i] = s.substring(i, N);

        }

        // sort them

        Arrays.sort(suffixes);

        // find longest repeated substring by comparing adjacent sorted suffixes

        String lrs = "";

        for (int i = 0; i < N - 1; i++) {

            String x = lcp(suffixes[i], suffixes[i+1]);

            if (x.length() > lrs.length())

                lrs = x;

        }

        return lrs;

    }

heap sort optimized code

static void HeapSort(int[] arr) {
// TODO Auto-generated method stub
for(int i=0; i<arr.length;i++)
{
System.out.print(" "+arr[i]);
createHeap(arr,i);
}

System.out.println("     ");
System.out.println("heap generated");
for(int i=0; i<arr.length;i++)
{
System.out.print(" "+arr[i]);
}
for(int last=arr.length-1;last>0;)
{
int temp =arr[0];
arr[0]= arr[last];
arr[last--]=temp;
if(last>0)
fixHeap(arr,last);
}
}



private static void fixHeap(int[] arr,int last)
{
int currentIndex = 0;
boolean isHeap = false;

while (!isHeap) {
int leftChildIndex = 2 * currentIndex + 1;
int rightChildIndex = 2 * currentIndex + 2;
int maxIndex = currentIndex;

if (leftChildIndex <= last &&
arr[maxIndex] < arr[leftChildIndex]) {
maxIndex = leftChildIndex;
}

if (rightChildIndex <= last &&
arr[maxIndex] < arr[rightChildIndex]) {
maxIndex = rightChildIndex;
}

if (maxIndex != currentIndex) {
// Swap list[currentIndex] with list[maxIndex]
int temp = arr[currentIndex];
arr[currentIndex] = arr[maxIndex];
arr[maxIndex] = temp;
currentIndex = maxIndex;
} else {
isHeap = true;
}
}
}

private static void createHeap(int[] arr,int p) {
// TODO Auto-generated method stub
int parent=p;
while(parent> 0 && arr[parent]>arr[(parent-1)/2])
{
int temp=arr[parent];
arr[parent]=arr[(parent-1)/2];
arr[(parent-1)/2]=temp;

parent=(parent-1)/2;

}
}

find submatrix with non zero element for a given matrix

 static void findSubMatix(int[][] mat, int size) {
        int imax = 0, jmax = 0, res = 1;
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                int d = 0, r = 0, max = 1;
                while (max + i < size && j + max < size) {
                    if (mat[i + max][j] == 1 && mat[i][j + max] == 1) {
                        max++;
                    } else {
                        break;
                    }
                }
                int x = max - 1;
                d = i + max - 1;
                r = j + max - 1;
                if (mat[d][r] == 1) {
                    x--;
                    while (x > 0) {
                        if (mat[d - x][r] == 1 && mat[d][r - x] == 1) {
                            x--;
                        } else {
                            break;
                        }
                    }
                }
                if (x == 0 && res < max) {
                    res = max;
                    imax = i;
                    jmax = j;
                }
            }
        }
        System.out.println("\nsize :" + res + "(" + imax + "," + jmax + ")");
        for (int a = imax; a <= imax + res - 1; a++) {
            System.out.println();
            for (int b = jmax; b <= jmax+res-1; b++) {
                System.out.print(mat[a][b]+" , ");
            }
        }
    }

    static public void main(String[] args) {
        int[][] mat = {
            {1, 0, 1, 1, 1, 0, 0, 1},
            {1, 1, 1, 1, 0, 1, 1, 1},
            {1, 1, 1, 1, 1, 1, 1, 1},
            {0, 1, 1, 0, 0, 0, 0, 1},
            {1, 1, 0, 0, 0, 0, 1, 1},
            {1, 1, 1, 1, 0, 0, 0, 1},
            {1, 1, 1, 1, 1, 1, 1, 1},
            {1, 1, 1, 1, 1, 1, 1, 1}
        };
        findSubMatix(mat, 8);
    }

sudoko

public class Sudoko {

    public static void main(String[] args) {
        main();
    }

    static void main() {
        Square[][] board = new Square[9][9];
        initBoard(board);
        placeNumbers(board);
        printBoard(board);
    }

    static void initBoard(Square[][] board) {
        int[][] b = init();

        for (int r = 0; r < board.length; r++) {

            for (int c = 0; c < board.length; c++) {
                Square cell = new Square();
                board[r][c] = cell;
                board[r][c].val = b[r][c];
            }
        }
        setPossibles(board);
    }

    static void placeNumbers(Square[][] b) {

        while (hasEmptySpace(b)) {
            makeMove(findMove(b), b);
        }
    }

    static void printBoard(Square[][] b) {

        for (int r = 0; r < b.length; r++) {
            System.out.println(" ");

            for (int c = 0; c < b.length; c++) {

                if (b[r][c].val == 0) {
                    System.out.print("   ");
                } else {
                    System.out.print(" " + b[r][c].val + " ");
                }
            }
        }
    }

    static Coord findMove(Square[][] b) {
        Coord co = new Coord();

        for (int r = 0; r < b.length; r++) {

            for (int c = 0; c < b.length; c++) {

                if (b[r][c].val == 0 && unique(b[r][c].possibles)) {
                    co.row = r;
                    co.col = c;
                }
            }
        }
        return co;
    }

    static void makeMove(Coord c, Square[][] b) {
        int num = value(b[c.row][c.col].possibles);
        b[c.row][c.col].val = num;
        removeImpossibles(num, c.row, c.col, b);
    }

    static int[][] init() {
        int[][] b = {{1, 0, 6, 0, 9, 4, 0, 0, 0},
        {8, 0, 2, 1, 0, 0, 0, 3, 0},
        {0, 0, 0, 0, 5, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 3, 0, 6},
        {3, 6, 0, 0, 2, 0, 0, 8, 4},
        {2, 0, 7, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 6, 0, 0, 0, 0},
        {0, 1, 0, 0, 0, 8, 5, 0, 2},
        {0, 0, 0, 5, 3, 0, 9, 0, 7}};
        return b;
    }

    static boolean hasEmptySpace(Square[][] b) {

        for (int r = 0; r < b.length; r++) {

            for (int c = 0; c < b.length; c++) {

                if (b[r][c].val == 0) {
                    return true;
                }
            }
        }
        return false;
    }

    static boolean unique(boolean[] list) {
        int count = 0;

        for (int i = 1; i < list.length; i++) {

            if (list[i]) {
                count++;
            }
        }
        return count == 1;
    }

    static int value(boolean[] list) {
        assert (unique(list)) :
                "you need a look ahead, as this is a hard game";

        for (int i = 1; i < 10; i++) {

            if (list[i]) {
                return i;
            }
        }
        return 0;
    }

    static void setPossibles(Square[][] b) {

        for (int r = 0; r < b.length; r++) {

            for (int c = 0; c < b.length; c++) {

                if (b[r][c].val != 0) {
                    removeImpossibles(b[r][c].val, r, c, b);
                }
            }
        }
    }

    static void removeImpossibles(int n, int r, int c, Square[][] b) {
        unSetInRow(n, r, b);
        unSetInCol(n, c, b);
        unSetInSquare(n, r, c, b);
    }

    static void unSetInRow(int n, int r, Square[][] b) {

        for (int i = 0; i < b.length; i++) {
            b[r][i].possibles[n] = false;
        }
    }

    static void unSetInCol(int n, int c, Square[][] b) {

        for (int i = 0; i < b.length; i++) {
            b[i][c].possibles[n] = false;
        }
    }

    static void unSetInSquare(int n, int r, int c, Square[][] s) {
        r = (r / 3) * 3;
        c = (c / 3) * 3;

        for (int i = r; i < r + 3; i++) {

            for (int j = c; j < c + 3; j++) {
                s[i][j].possibles[n] = false;
            }
        }
    }

    static void printSquare(Square s) {
        System.out.print("val = " + s.val);

        for (int i = 0; i < s.possibles.length; i++) {

            if (s.possibles[i]) {
                System.out.print("t ");
            } else {
                System.out.print("f ");
            }
        }
        System.out.println();
    }

    static void printBoardStructure(Square[][] b) {

        for (int r = 0; r < b.length; r++) {

            for (int c = 0; c < b.length; c++) {
                printSquare(b[r][c]);
            }
        }
    }
}

class Square {

    int val = 0;
    boolean[] possibles = {true, true, true, true, true, true, true, true, true, true};
}

class Coord {

    int row = 0;
    int col = 0;
}

WAP to find maximum possible pallendrome out of a given string

 static ArrayList<String> findMaxPalindrome(String str) {
        ArrayList<String> result = new ArrayList<String>();
        char[] ch = str.toCharArray();
        int ld = 0, rd = 0;
        for (int i = 0; i < ch.length - 1; i++) {
            if ((ch[i] == ch[i + 1]) || (i > 0 && ch[i - 1] == ch[i + 1])) {
                if (ch[i] == ch[i + 1]) {
                    ld = i - 1;
                    do{i++;}while(ch[i]==ch[i+1]);
                    rd = i + 1;
                } else if (i > 0) {
                    ld = i - 1;
                    rd = i + 1;
                }
                while (ld >= 0 && rd < ch.length) {
                    if (ch[ld] != ch[rd]) break;
                    ld--;   rd++;
                }
                if (rd - ld  > 3)
                    result.add(str.substring(ld+1, rd));
            }
        }
        return result;
    }