Find first non repeating character from a string

Given a string find first non repeating character from a string.

We can use HashMap to find the duplicates. To find out first non repeated character, iterate the string to find character which is not repeated. 
 

public class Solution{
    public static void FindFirstNonRepeatingChar(String input){
        if(input.length() > 0){
            HashMap charMap = new HashMap<>();
            for(char ch : input.toCharArray()){
                if(charMap.containsKey(ch))
                    charMap.put(ch, Boolean.TRUE);
                else
                    charMap.put(ch, Boolean.FALSE);
            }

            for (char ch : input.toCharArray()){
                if(charMap.get(ch) == Boolean.FALSE) {
                    System.out.println("First Non Repeating Character : " + ch);
                    return;
                }
            }
        }
        System.out.println("Couldn't find Non Repeating Character");
    }

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

Comments are welcome.

Find out maximum of subarry

Given an array and an size of sub array as k, find out maximum for every contiguous subarray of size k.
The problem looks simple but brute force would require n * k complexity to find out max in every subarray of length k.
We can improve complexity by introducing simple check as below 

• First find max in array of length k.
• For every next element in array post length k, check if its maximum than current max, if yer it becomes new max of current sub array.
• If not then we need new max of current sub array... repeat step 2 & 3 this till end of array.

Worst case complexity of this approach would be n *k.

Code below implements this approach.

  
//Maximum of subarray
public class Solution {
    private static int FindMax(int[] input, int k, int start){
        if(start >= 0) {
            int max_index = start;
            for (int i = start; (i < input.length) && i < start + k; i++) {
                if (input[i] > input[max_index])
                    max_index = i;
            }
            return max_index;
        }
        return -1;
    }

    public static void MaxOfSubArrays(int [] input, int k) {
        if(input.length > k) {
            int max_index = FindMax(input, k, 0);
            int max = input[max_index];

            System.out.print(max + " ");

            for (int i = k; i < input.length; i++) {
                if (input[i] > max) {
                    max = input[i];
                    max_index = i;
                }
                else if (max_index <= i-k ) {
                    max_index = FindMax(input, k, i+1 - k);
                    max = input[max_index];
                }

                System.out.print(max + " ");
            }
        }
    }
    public static void main(String[] args){
        int [] input = {9, 8, 7, 6, 5, 12, 10, 3, 11};
        MaxOfSubArrays(input, 3);
    }
}

Comments are welcome.

Expression evaluator

Given list of expressions

a = 10
b = a + 1
c = a + b
d = c * b + a * c

Print out value of last variable (in our example, it is d). 

First we would need a expression evaluator which will evaluate individual expression. 
Solution below uses two stacks for expression evaluation one for operator and one for operand. First we evaluate operations such as *, / which are high priority then evaluate +, - and = operators in second pass.

//The code below considers
//1. Only int values
//2. Only supports +, -, *, /, = operators  
public class Solution{

    private HashMap VarMap;
    Stack operandStack;
    Stack operatorStack;

    public  Solution(){
        VarMap = new HashMap<>();
        operandStack = new Stack<>();
        operatorStack = new Stack<>();
    }

    public int EvaluateExpression(String statement){
        return Evaluator(statement.replace(" ", ""));
    }

    private int GetNextOperand(String expression, int start){
        int i = start;
        for(; i < expression.length(); i++){
            char operator = expression.charAt(i);
            if(operator =='+' || operator == '-' || operator== '/' || operator == '*' || operator == '=')
               break;
        }
        return i;
    }

    private int EvaluateHighPriorityOpearators(){
        if(operatorStack.empty())
            return 0;
        char lastOperator = operatorStack.peek();
        switch (lastOperator){
            case '+':
            case '-':
                break;
            case '*': {
                String operand2 = operandStack.pop();
                String operand1 = operandStack.pop();

                String resultStr = operand1 + "*" + operand2;
                int result = VarMap.get(operand1) * VarMap.get(operand2);
                VarMap.put(resultStr, result);
                operandStack.push(resultStr);
                operatorStack.pop();
                return result;
            }
            case '/': {
                String operand2 = operandStack.pop();
                String operand1 = operandStack.pop();

                String resultStr = operand1 + "/" + operand2;
                int result = VarMap.get(operand1) / VarMap.get(operand2);
                VarMap.put(resultStr, result);
                operandStack.push(resultStr);
                operatorStack.pop();
                return result;
            }
        }
        return 0;
    }

    private int EvaluateNormalPriorityOperators() {
        if (operandStack.empty())
            return 0;
        int result = 0;
        if( VarMap.containsKey(operandStack.peek()) )
            result = VarMap.get(operandStack.pop());
        else
            result = Integer.parseInt(operandStack.pop());

        while (!operatorStack.empty()) {
            char lastOperator = operatorStack.pop();
            String operand1 = operandStack.pop();
            int val = 0;
            if (VarMap.containsKey(operand1))
                val = VarMap.get(operand1);
            else
                if(lastOperator != '=')
                    val = Integer.parseInt(operand1);

            switch (lastOperator) {
                case '+':
                    result += val;
                    break;
                case '-':
                    result -= val;
                    break;
                case '=':
                    VarMap.put(operand1, result);
                    break;
            }
        }
        return result;
    }

    private int Evaluator(String expression){
        int result = 0;
        String operand = "";
        char operator = ' ';
        for(int start = 0; start < expression.length(); ){
            int i = GetNextOperand(expression, start);
            operand = expression.substring(start, i);
            operandStack.push(operand);
            result = EvaluateHighPriorityOpearators();
            if (i < expression.length()){
                operator = expression.charAt(i);
                operatorStack.push(operator);
            }
            start = i + 1;
        }

        if(!operandStack.isEmpty()){
            result = EvaluateNormalPriorityOperators();
        }
        return result;
    }

    public static void main(String[] args) {
        List input = new ArrayList<>();
        input.add("a = 10");
        input.add("b = a + 1");
        input.add("c = a + b");
        input.add("d = c * b + a * b");

        Solution sol = new Solution();

        for (int i = 0; i < input.size()-1; i++){
            sol.EvaluateExpression(input.get(i));
        }
        System.out.println(sol.EvaluateExpression(input.get(input.size()-1)));
    }
}

//Output of above code
341

Question referenced from geeksforgeeks
Comments are welcome.

Find out order between characters from given dictionary words

Given a dictionary of unknown language and characters. Find out order between characters.
Example : "ab", "bbd", "bed", "bcd", "ce", "de"
Output : a, b, e, c, d

Finding out the sorting order using brute force would be tedious task. We can use topological sorting for this.

We will create a graph having characters as node in graph and have edge between two character if any character appear next to other character. 

Solution below implements full topological sorting approach, where we create a graph and then search the character order using topological sorting.
Graph uses adjacency list implementation.

class Graph{
    int V;
    int vCnt;

    class Node{
        public char data;
        public Node next;

        public Node(char ch, Node nxt){
            data = ch;
            next = nxt;
        }
    }

    Node[] adj;

    public Graph(int v){
        V = v;
        vCnt = 0;
        adj = new Node[v];
    }

    public void AddEdge(char v, char w){
        Node n = SearchNode(v);
        while (n.next != null){
            if(n.next.data == w)
                return;
            n = n.next;
        }
        n.next = new Node(w, null);
        Node m = SearchNode(w);
    }

    private Node SearchNode(char ch){
        for (int i = 0; i < vCnt; i++){
            if(adj[i].data == ch){
                return adj[i];
            }
        }
        adj[vCnt] = new Node(ch, null);
        vCnt++;
        return adj[vCnt-1];
    }

    private void TopologicalUtil(char ch, HashMap visited, Stack stack){
        visited.put(ch, Boolean.TRUE);
        Node n = SearchNode(ch);
        while (n.next != null){
            if(visited.get(n.next.data) == Boolean.FALSE )
                TopologicalUtil(n.next.data, visited, stack);
            n = n.next;
        }
        stack.push(ch);
    }

    public void TopologicalSort(){
        Stack stack = new Stack();
        HashMap visited = new HashMap();
        for(int i = 0; i < vCnt; i++ ){
            visited.put(adj[i].data,Boolean.FALSE);
        }

        for(int i = 0; i < vCnt; i++ ){
            if(visited.get(adj[i].data) == Boolean.FALSE )
                TopologicalUtil(adj[i].data, visited, stack);
        }

        while (!stack.isEmpty()){
            System.out.print(stack.pop() + ", ");
        }
    }
}

public class Solution{

    public static void main(String[] args) {
        List input = new ArrayList<>();
        input.add("ab");
        input.add("bbd");
        input.add("bed");
        input.add("bcd");
        input.add("ce");
        input.add("de");

        Graph g = new Graph(5);

        for (int i = 0; i < input.size()-1; i++) {
            String str = input.get(i);
            String str2 = input.get(i+1);
            if(str.charAt(0) != str2.charAt(0)) {
                char v = str.charAt(0);
                char w = str2.charAt(0);
                g.AddEdge(v, w);
            }
        }

        for (int i = 0; i < input.size()-1; i++){
            String str = input.get(i);
            String str2 = input.get(i+1);
            if(str.charAt(0) == str2.charAt(0)) {
                for (int j = 1; j < Math.min(str.length(), str2.length()); j++) {
                    if(str.charAt(j) != str2.charAt(j)) {
                        char v = str.charAt(j);
                        char w = str2.charAt(j);
                        g.AddEdge(v, w);
                    }
                }
            }
        }

        g.TopologicalSort();
    }
}

Problem referenced from geeksforgeeks.

Find minimum string containing given pattern

Given two string input and pattern. Find minimum window in input which contains all characters from string pattern. E.g : Consider input as "axcerdndnfdkgdfgn" and pattern as "ngdf". Pattern can be found at two instances 8 -12 or 13-16 indices. So minimum sliding windows becomes 13-16.


If there is single instance then problem becomes simple but if there are multiple instances we would need minimum of those.

 
//Below code first find sliding windows then finds minimum of those.
class Solution {

    public  int startIndex;
    public  int min;
    public  int max;

    public boolean getSlidingWindow(String input, String pattern){
        max = -1;
        HashMap charSet = new HashMap();

        for(char ch : pattern.toCharArray()){
            charSet.put(ch, 0);
        }

        PriorityQueue pq1 = new PriorityQueue();

        int soFarCharacters = charSet.size();
        int count = startIndex;
        for (; count < input.length() ; count++){
            char ch = input.charAt(count);
            if(charSet.containsKey(ch)){
                int value = charSet.get(ch);
                if(value == 0){
                    charSet.put(ch, 1);
                    soFarCharacters--;
                }

                if(pq1.size() > 0 && input.charAt(pq1.peek()) == ch ){
                    pq1.poll();
                }
                pq1.offer(count);
                if(count > max) max = count;
            }
            if(soFarCharacters == 0)
                break;
        }
        startIndex = count;
        if(soFarCharacters == 0) {
            min = pq1.peek();
            return true;
        }
        return false;
    }

    public static void main(String[] args) {
        String input = "axcerdndnfdkgdfgn";
        String pattern = "ngdf";

        int start = 0;
        int end = input.length();
        boolean found = false;

        Solution sol = new Solution();
        sol.startIndex = 0;
        sol.min = input.length();
        sol.max = -1;

        while (sol.getSlidingWindow(input, pattern )){
            if(end - start > sol.max - sol.min){
                end = sol.max;
                start = sol.min;
            }
            found = true;
        }
        if(found)
            System.out.println("Minimum Sliding Window : " + start + " To " + end);
    }
}

//Output of above code
Minimum Sliding Window : 13 To 16

Question referenced from geeksforgeeks

Valentine's Day Gift

Roman loved diamonds. Monica decided to give him a beautiful gift on Valentine's Day. Her idea of diamonds was different though. She lit up all the windows of her rectangular building with N floors and M windows on each floor, with 2 shapes - / or \ . According to her, a diamond was made when such a shape was created:

/ \ 
\ /

Given the shape of lights in all the windows, help Roman count the number of diamonds formed. Note: The components of the diamond should be adjacent to each other. Input: First line contains T - the number of testcases. For each testcase, First line contains 2 space-separated positive integers - N and M - the no. of floors in the building and the no. of windows on each floor respectively. N lines follow - each line contains M space-separated characters. Every character is either \ or / . Output: Print a single integer - the total no. of diamonds formed. Constraints: 1 ≤ T ≤ 5 2 ≤ N, M ≤ 1000 Sample Input(Plaintext Link)

 1
2 4
/ \ / \
\ / \ /

Output:
2

Solutions

 public class Solution {  
   public static void main(String[] args) throws IOException {  
     Scanner in = new Scanner(System.in);  
     int t;  
     t = in.nextInt();  
     int m, n;  
     for (int i = 0; i < t; i++) {  
       n = in.nextInt();  
       m = in.nextInt();  
       String[][] st1 = new String[n][m];  
       in.nextLine();  
       for (int j = 0; j < n; j++) {  
         st1[j] = in.nextLine().split(" ");  
       }  
       int count = 0;  
       for (int j = 0; j < n - 1; j++) {  
         for (int k = 0; k < m - 1; k++) {  
           if (st1[j][k].equals("/") && st1[j][k + 1].equals("\\")) {  
             if (st1[j + 1][k].equals("\\") && st1[j + 1][k + 1].equals("/")) {  
               count++;  
             }  
           }  
         }  
       }  
       System.out.println(count);  
     }  
   }  
 }  

Comments are welcome.

Find path having maximum gold in matrix

Given a gold mine of n*m dimension. Each field in this mine contains an integer which is amount of gold in tons. Initially miner is in first column but could be at any row i. He can move only right, right up , right down. Find out maximum amount of gold he can collect.

Approach 1: Brute force

For every row find all possible paths and calculate the maximum gold. Find all the paths recursively and return maximum gold.

Approach 2: Dynamic Programming

During brute force approach we search same path multiple times, instead we can store the result and reuse the result for next iterations.

Code below implements approach 2.

class Solution {

    private static boolean isValidMove(int x, int y, int[][] matrix){
        if(x >= 0 && y >= 0){
            if(x < matrix.length && y < matrix[0].length ){
                return true;
            }
        }
        return false;
    }

    public static int findMaxGold(int[][] mines, int x, int y, int[][] storage){
        if(isValidMove(x, y, mines)){
            if(storage[x][y] != -1)
                return  storage[x][y];
            int rightGold = mines[x][y] + findMaxGold(mines, x, y+1, storage);
            int rightUpGold = mines[x][y] + findMaxGold(mines, x-1, y+1, storage);
            int rightDownGold = mines[x][y] + findMaxGold(mines, x+1, y+1, storage);
            int max = Math.max(rightGold, Math.max(rightDownGold, rightUpGold));
            storage[x][y] = max;
            return max;
        }
        return 0;
    }

    public static void main(String[] args) {
        int[][] mines ={{1, 3, 5, 19},
                         {2, 5, 6, 8},
                         {9, 6, 6, 12},
                         {14, 2, 4, 22},
                         {0,  2, 4, 32}};
        int maxGold = Integer.MIN_VALUE;
        int[][] storage = new int [mines.length][mines[0].length];
        for (int i=0; i < storage.length; i++) {
            for(int j=0; j < storage[0].length;j++)
                storage[i][j] = -1;
        }

        for (int i=0; i < mines.length; i++){
            maxGold = Math.max(maxGold, findMaxGold(mines, i, 0, storage));
        }
        System.out.println("MAX Gold in Mine : " + maxGold);
    }
}