Find the first non-repeated character in an input String – Java Implementation

This class is a demonstration of how we can find the firs non-repeated character in a given string. The java code below is implemented with a flag for case sensitivity and shows you examples of how to use it.

For a sample text “This is that”, the first non-repeated character is “a” if your cases are not sensitive, however, if you cases are sensitive, the first non repeated character is “T”

package com.icodejava.blog.published;

import java.util.HashMap;
import java.util.Map;

/**
 * 
 * @author Kushal Paudyal 
 * Created on: 01/05/2017 
 * Last Modified on: 01/05/2017
 *
 * This class demonstrates how we can find first non repeated character
 * in any given String. We will test for Case Sensitivity as well
 */

public class NonRepeatedCharacterFinder {

	final static boolean CASE_SENSITIVE = true;

	public static void main(String args[]) {
		String str = "Java Blog for junior Students";

		findFirstNonRepeatedCharacter(str, CASE_SENSITIVE);
		findFirstNonRepeatedCharacter(str, !CASE_SENSITIVE);

		str = "Apple is pretty yummy and healthy";

		findFirstNonRepeatedCharacter(str, CASE_SENSITIVE);
		findFirstNonRepeatedCharacter(str, !CASE_SENSITIVE);
		

		str = "ABba";
		findFirstNonRepeatedCharacter(str, CASE_SENSITIVE);
		findFirstNonRepeatedCharacter(str, !CASE_SENSITIVE);
	}

	private static void findFirstNonRepeatedCharacter(String originalString, boolean caseSensitive) {
		String str = originalString;

		if (str == null) {
			System.out.println("Not a valid string");
		}

		if (!caseSensitive) {
			str = str.toLowerCase();
		}

		Map<Character, Integer> countMap = new HashMap<Character, Integer>();

		// loop through the characters and find the character count
		for (int i = 0; i < str.length(); i++) {
			Character character = new Character(str.charAt(i));
			if (countMap.containsKey(character)) {
				Integer charCount = countMap.get(character);
				countMap.put(character, ++charCount);
			} else {
				countMap.put(character, 1);
			}
		}

		// Now find the first character that has a count of 1. Please note, we have iterated through the String characters. 
		// You can alternately iterate through the keys and find the corresponding values.
		boolean found = false;
		for (int i = 0; i < str.length(); i++) {
			char currentChar = str.charAt(i);
			if (countMap.get(currentChar) == 1) {
				System.out.println("FOUND. The first non repeated character in the String " + currentChar
						+ " (Case Sensitive: " + caseSensitive + ", String: " + originalString + ")");
				found = true;
				break;
			}

		}

		if (!found) {
			System.out.println("NOT FOUND: Non repeated character not found in the String." + " (Case Sensitive: "
					+ caseSensitive + ", String: " + originalString + ")");
		}

	}

}

OUTPUT

FOUND. The first non repeated character in the String J (Case Sensitive: true, String: Java Blog for junior Students)
FOUND. The first non repeated character in the String v (Case Sensitive: false, String: Java Blog for junior Students)
FOUND. The first non repeated character in the String A (Case Sensitive: true, String: Apple is pretty yummy and healthy)
FOUND. The first non repeated character in the String i (Case Sensitive: false, String: Apple is pretty yummy and healthy)
FOUND. The first non repeated character in the String A (Case Sensitive: true, String: ABba)
NOT FOUND: Non repeated character not found in the String. (Case Sensitive: false, String: ABba)

Array Max Integer Finder (With Big O Analysis)

This tutorial shows you an implementation of three different methods of searching for the maximum number in an Integer array. The array is assumed to hold positive integers.

  1. First method findMaxCompareMax() assumes the first number on the array to be maximum and the loops through other numbers in sequence and replaces the current maximum with the new maximum. When all the elements are checked, we have a maximum number.
  2. The second method findMaxCompareAll() takes an array element and compares it with every other element in the array to see if it is maximum. If it is not, then it proceeds with the next element.
  3. The third method findMaxCompareAfterIndex() This method takes an array element and compare it with other elements in the array to see if it is maximum. If it is not, then it proceeds with the next element. However, this method does not compare every element from the beginning. To avoid redundant comparing, it only compares with the remaining elements in the array (i.e. position + 1 onwards)

Check the code comments for the Big O Analysis of these three methods.

package com.icodejava.blog.published.search;

import java.util.Arrays;

/**
 * 
 * This class is used to demonstrate 3 different ways of finding a maximum
 * number in an Integer Array holding positive integer numbers.
 * 
 * Also provides a Big O analysis.
 */
public class MaxIntegerFinder {

    public static void main(String args[]) {

        int[] numbers = {5, 4, 9, 2, 2, 1, 10, 21, 6 };
        
        System.out.println("Source Array " + Arrays.toString(numbers));

        findMaxCompareMax(numbers);

        findMaxCompareAll(numbers);

        findMaxCompareAfterIndex(numbers);

    }


    /**
     * This method assumes the first number on the array to be the maximum
     * You can also assume the last one to be the max and compare it in reverse.
     * It then loops through other numbers in the array and replaces the 
     * current maximum with the new maximum it finds.
     * 
     * Complexity: O(n) where n is the number of elements in the array
     */
    private static int findMaxCompareMax(int[] numbers) {

        if (numbers.length < 1 ) {
            return 0;
        }
        
        int currentMax = numbers[0];
        for (int i = 1 ; i < numbers.length; i++) { if(numbers[i] > currentMax) {
                currentMax = numbers[i];
            }
        }
        
        System.out.println("Max Number using findMaxCompareMax -> " + currentMax);
        return currentMax;
        
    }
    
    /**
     * This method takes an array element and compare it with 
     * every other element in the array to see if it is maximum.
     * 
     * If it is not, then it proceeds with the next element
     * 
     * Complexity: O(n^2) in worst case and O(n) in best case 
     * where n is the number of elements in the array
     * 
     * Best case scenario is where the first element itself is maximum
     * Worst case scenario is where the last element is maximum.
     */
    private static int findMaxCompareAll(int[] numbers) {

        if (numbers.length < 1) {
            return 0;
        }

        int max = -1;

        for (int i = 0; i < numbers.length; i++) {
            for (int j = 0; j < numbers.length; j++) {
                if (max < numbers[j]) { max = numbers[j]; break; } } } System.out.println("Max Number using findMaxCompareAll -> " + max);
        return max;

    }
    
    /**
     * This method takes an array element and compare it with 
     * other elements in the array to see if it is maximum.
     * 
     * If it is not, then it proceeds with the next element. 
     * 
     * However, this method does not compare every element from the beginning. 
     * To avoid redundant comparing, it only compares with the remaining elements
     * in the array (i.e. position + 1 onwards)
     * 
     * Complexity: O(n^2) in worst case and O(n) in best case 
     * where n is the number of elements in the array
     * 
     * Best case scenario is where the first element itself is maximum
     * Worst case scenario is where the last element is maximum.
     */
    private static int findMaxCompareAfterIndex(int[] numbers) {

        if (numbers.length < 1 ) {
            return 0;
        }
        
        int max=-1;
        
        for (int i = 0 ; i < numbers.length; i++) {
            for(int j = i ; j< numbers.length; j++) {
                if(max < numbers [j]) { max = numbers[j]; break; } } } System.out.println("Max Number using findMaxCompareAfterIndex -> " + max);
        return max;
    }

}

OUTPUT:

Source Array [5, 4, 9, 2, 2, 1, 10, 21, 6]
Max Number using findMaxCompareMax -> 21
Max Number using findMaxCompareAll -> 21
Max Number using findMaxCompareAfterIndex -> 21

A Basic Implementation of Binary Tree in Java

A Binary Tree simply can be defined in Java as a node that holds a value for itself and holds reference to a left child node and a right child node. The binary tree can have nodes that have a maximum of 2 children. As you can see in the example below, I have defined the value to be of type Comparable, so that it can be any object that can be compare for less than, greater than or equals. However, if you are going to only store either integers or Strings, for example, you can change the data type to int or String as needed.

The following is a very simple implementation of this concept.

Note: – if the binary tree has left nodes only or right nodes only, it becomes a singly linked list.

package com.icodejava.blog.published.datastructure;
/**
* @author Kushal Paudyal
* Created on 12/5/2016
* Last Modified on 12/5/2016
*
* Binary Tree Node representation.
* - Node has a value, a left node and a right node.
* - Single node, when created, has left and right node as null.
*/
@SuppressWarnings("rawtypes")
class BinaryTreeNode {
Comparable value;
BinaryTreeNode left;
BinaryTreeNode right;

public BinaryTreeNode(Comparable value) {
this.value = value;
this.left = null;
this.right = null;
}

public Comparable getValue() {
return value;
}

public void setValue(Comparable value) {
this.value = value;
}

public BinaryTreeNode getLeft() {
return left;
}

public void setLeft(BinaryTreeNode left) {
this.left = left;
}

public BinaryTreeNode getRight() {
return right;
}

public void setRight(BinaryTreeNode right) {
this.right = right;
}

}