Sunday, September 20, 2015

ArrayList class lastIndexOf method

ArrayList class lastIndexOf() method

This is 12th post in series of ArrayList class. Previously we have seen ArrayList introduction, ArrayList class constructors, add() method, addAll() method, clear() method, indexOf() method, contains() method, forEach() method, get(), isEmpty() and iterator() method.

In this post we will see lastIndexOf() method. We saw indexOf() method and it returns index of the object if it exists and -1 if object does not exists.

lastIndexOf() is similar to indexOf() method as lastIndexOf() method starts to search for object in reverse way. So it returns the highest index of specified element if found else it returns -1.

Below is the code taken from JDK.
    public int lastIndexOf(Object o) {
        if (o == null) {
            for (int i = size-1; i >= 0; i--)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = size-1; i >= 0; i--)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }

The for loop used is reverse. It traverses from end to beginning of List. As soon as it finds the element it returns the index. If it is not able to find it returns -1.

Below is the code that demonstrate the lastIndexOf() method

package org.example.collections.list.arraylist;

import java.util.ArrayList;
import java.util.List;

public class ArrayListlastIndexOf {

      /**
       * This method is used to fill Integer values
       * to List using add() method.
       * */
      public List<Integer> numbers(){
           
            List<Integer> numbers = new ArrayList<Integer>();
            numbers.add(10);
            numbers.add(12);
            numbers.add(5);
            numbers.add(10);
            numbers.add(7);
            return numbers;
      }
     
      /**
       * This method takes List and candidate as input.
       * It searches for the candidate in List and returns
       * the index.
       *
       * @param numbers
       * @param number
       * */
      public void lastIndexofDemo(List<Integer> numbers, int number){

            int index = numbers.lastIndexOf(number);
            System.out.println("Index for "+number+" is:: "+index);
      }
     
      public static void main(String[] args) {
            ArrayListlastIndexOf lastIndexOf = new ArrayListlastIndexOf();
            List<Integer> numbers = lastIndexOf.numbers();
            //Prints 3
            lastIndexOf.lastIndexofDemo(numbers, 10);
           
            //Prints 4
            lastIndexOf.lastIndexofDemo(numbers, 7);

            //Not Found
            //Prints -1
            lastIndexOf.lastIndexofDemo(numbers, 17);
      }
}

Output
Index for 10 is:: 3
Index for 7 is:: 4
Index for 17 is:: -1

That’s all on lastIndexOf() method. In next post we will see listIterator() method. It is better version of iterator() because it allows several different methods like add(), hasNext(), hasPrevious(), next(), nextIndex(), previous(), previousIndex(), remove() and set() method.


Saturday, September 19, 2015

Maximum occurring character in String

Maximum occurring character in String

In previous post (Count Frequency of Characters in String) we saw how to count the frequency of all the characters in String.

In this post we will extend that concept to find the maximum occurrence of character in String. Finding maximum occurrence in String requires calculating the frequency of all the characters in String. Hence we can use the code of previous post.

Let us first try with array. Below is the code that gives us the frequency of each character in String.

public static int[] characterCountByArray(String str) {

      if (str == null) {
            throw new NullPointerException("String must not be null");
      } else if (str.length() == 0) {
            return new int[] {};
      }
      int[] aux = new int[256];
      for (int i = 0; i < str.length(); i++) {
            aux[str.charAt(i)]++;
      }
      return aux;
}

Now let us write a getMaxIndex() which will get index of max value in array.

public static int[] characterCountByArray(String str) {

      if (str == null) {
            throw new NullPointerException("String must not be null");
      } else if (str.length() == 0) {
            return new int[] {};
      }
      int[] aux = new int[256];
      for (int i = 0; i < str.length(); i++) {
            aux[str.charAt(i)]++;
      }
      getMaxIndex(aux);
      return aux;
}

public static char getMaxIndex(int[] aux){
      int max = aux[0];
      char ch = 0;
      for (int i = 0; i < aux.length; i++) {
            if (aux[i] > 0 && aux[i] > max) {
                  max = aux[i];
                  ch = (char) i;
            }
      }
      System.out.println(ch + " " + max);
      return ch;
}

Input
Output
“Mississippi”
i 4

Output i 4
Means character ‘i’ is repeated 4 times which is highest.

Character ‘s’ is also repeated 4 times by character ‘i’ comes before character ‘s’ so output is ‘i’. So output is in alphabetical order.

To do same using LinkedHashMap below is the code.

public static
Map<Character, Integer> characterCountByLinkedHashMap(String str) {

      if (str == null) {
            throw new NullPointerException("String must not be null");
      } else if (str.length() == 0) {
            return new LinkedHashMap<>();
      }
   Map<Character, Integer> map = new LinkedHashMap<Character, Integer>();
      for (Character ch : str.toCharArray()) {
            if (map.containsKey(ch)) {
                  map.put(ch, map.get(ch) + 1);
            } else {
                  map.put(ch, 1);
            }
      }
      //Find max here.
      Set<Map.Entry<Character, Integer>> entries = map.entrySet();
      int max = Integer.MIN_VALUE;
      Entry<Character, Integer> value = null;
      for (Entry<Character, Integer> entry : entries) {
            if (max < entry.getValue()) {
                  max = entry.getValue();
                  value = entry;
            }
      }
      System.out.println(value);
      return map;
}



Count frequency of all characters in String

Count frequency of all characters in String

In this String relation question we are supposed to find the frequency of every character that comes in String.

For example:

Input
Output
null
NullPointerException
“”

“laptop”
l=1, a=1, p=2, t=1, o=1
“mississippi”
m=1, i=4, s=4, p=2
“God”
G=1, o=1, d=1


We will first use HashMap for our solution. We will scan entire String character by character and insert them in HashMap. If the character does not exist in it then we will set value to 1. If it exists then we will add 1 to the previous value.

public static
Map<Character, Integer> characterCountByHashMap(String str) {

       if (str == null) {
           throw new NullPointerException("Input Parameter must not be null");
       } else if (str.length() == 0) {
              return new HashMap<>();
       }
       Map<Character, Integer> map = new HashMap<Character, Integer>();
       for (Character ch : str.toCharArray()) {

              if (map.containsKey(ch)) {
                     map.put(ch, map.get(ch) + 1);
              } else {
                     map.put(ch, 1);
              }
       }
       System.out.println(map);
       return map;
}

Entire class for character count by HashMap.

package com.learninghorizon.blog.strings;

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

public class CharacterCount {

       public static void main(String[] args) {

              String str = "mississippi";
              characterCountByHashMap(str);
       }

   public static
   Map<Character, Integer> characterCountByHashMap(String str) {

       if (str == null) {
          throw new NullPointerException("Input Parameter must not be null");
       } else if (str.length() == 0) {
               return new HashMap<>();
       }
       Map<Character, Integer> map = new HashMap<Character, Integer>();
       for (Character ch : str.toCharArray()) {

              if (map.containsKey(ch)) {
                    map.put(ch, map.get(ch) + 1);
              } else {
                    map.put(ch, 1);
              }
       }
       System.out.println(map);
       return map;
       }
}

Output:
{p=2, s=4, i=4, m=1}

HashMap does not maintain the order of insertion. To do so we can replace HashMap with LinkedHashMap.

Below the solution implemented by LinkedHashMap.

       public static
       Map<Character, Integer> characterCountByLinkedHashMap(String str) {

       if (str == null) {
          throw new NullPointerException("Input Parameter must not be null");
       } else if (str.length() == 0) {
              return new LinkedHashMap<>();
       }
       Map<Character, Integer> map = new LinkedHashMap<Character, Integer>();
       for (Character ch : str.toCharArray()) {

              if (map.containsKey(ch)) {
                    map.put(ch, map.get(ch) + 1);
              } else {
                    map.put(ch, 1);
              }
       }
       return map;
       }

Output:
{m=1, i=4, s=4, p=2}


Now, let us implement this solution by array. We will declare the array of int[] of length 256. Why 256? Because the length of ASCII is 256.

/**
 * We are declaring int[] of 256 because ASCII length is 256.
 * */
public static int[] characterCountByArray(String str) {

       if (str == null) {
       throw new NullPointerException("Input Parameter must not be null");
       } else if (str.length() == 0) {
              return new int[] {};
       }
       int[] aux = new int[256];
       for (int i = 0; i < str.length(); i++) {
              aux[str.charAt(i)]++;
       }
       return aux;
}

Below is the entire class which uses int[] array to determine the count of each character in string.
public class CharacterCount {

       public static void main(String[] args) {

              String str = "mississippi";
                           
              int[] aux = characterCountByArray(str);
              for (int i = 0; i < aux.length; i++) {
                     if (aux[i] > 0) {
                           System.out.println((char)i + " " + aux[i]);
                     }
              }
       }

/**
        * We are declaring int[] of 256 because ASCII length is 256.
        * */
       public static int[] characterCountByArray(String str) {

          if (str == null) {
            throw new NullPointerException("Input Parameter must not be null");
          } else if (str.length() == 0) {
                return new int[] {};
          }
          int[] aux = new int[256];
          for (int i = 0; i < str.length(); i++) {
                aux[str.charAt(i)]++;
          }
          return aux;
       }
}

Output
i 4
m 1
p 2
s 4

Below is the entire program that uses HashMap, LinkedHashMap and int[] array.

package com.learninghorizon.blog.strings;

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

public class CharacterCount {

       public static void main(String[] args) {

              String str = "mississippi";
              System.out.println(characterCountByHashMap(str));
              System.out.println();
             
              System.out.println(characterCountByLinkedHashMap(str));
              System.out.println();
             
              int[] aux = characterCountByArray(str);
              for (int i = 0; i < aux.length; i++) {
                     if (aux[i] > 0) {
                           System.out.println((char)i + " " + aux[i]);
                     }
              }
       }

       public static
Map<Character, Integer> characterCountByHashMap(String str) {

              if (str == null) {
             throw new NullPointerException("Input Parameter must not be null");
              } else if (str.length() == 0) {
                     return new HashMap<>();
              }
              Map<Character, Integer> map = new HashMap<Character, Integer>();
              for (Character ch : str.toCharArray()) {

                     if (map.containsKey(ch)) {
                           map.put(ch, map.get(ch) + 1);
                     } else {
                           map.put(ch, 1);
                     }
              }
              System.out.println(map);
              return map;
       }

       public static
 Map<Character, Integer> characterCountByLinkedHashMap(String str) {

           if (str == null) {
             throw new NullPointerException("Input Parameter must not be null");
           } else if (str.length() == 0) {
                     return new LinkedHashMap<>();
           }
         Map<Character, Integer> map = new LinkedHashMap<Character, Integer>();
           for (Character ch : str.toCharArray()) {

               if (map.containsKey(ch)) {
                  map.put(ch, map.get(ch) + 1);
               } else {
                  map.put(ch, 1);
               }
           }
           return map;
       }
      
       /**
        * We are declaring int[] of 256 because ASCII length is 256.
        * */
       public static int[] characterCountByArray(String str) {

           if (str == null) {
             throw new NullPointerException("Input Parameter must not be null");
           } else if (str.length() == 0) {
                 return new int[] {};
           }
           int[] aux = new int[256];
           for (int i = 0; i < str.length(); i++) {
                 aux[str.charAt(i)]++;
           }
           return aux;
       }
}

Read how to traverse Map in 5 ways. Check if 2 Strings are anagrams of each other 4 ways.  Find first non-repeating character in String. Reverse a String in 4 different ways.

Ads Inside Post