Rocks and Diamonds

In this post I want to tell about one simple programming task with solving in Java.

Suppose we have two strings with latin symbols out of order. First string may have duplicates and that string we call Rocks. Second string have no duplicates and we call it Diamonds. Our task to find out how many Diamonds exist in Rocks. Every symbol in second string is diamond.

If we want to use brute forse it will be not very effective. In that case we need to iterate full Rocks as many times as Diamonds exist in second string and we need to iterate the whole Rocks - from beginning to end.

To become more efficient we will to execute two preparations - sort Rocks and Diamonds alphabetically.

Now we have two sorted strings. Let begin iterate throught Diamonds and for every Diamond we iterate Rocks, but not the whole - when we found Diamond in Rock we increment our result counter, then take next Rock we check if it more then Diamond alphabetically. If it is then we take next Diamond because previous Diamond will not appear in rest Rocks - thay sorted and will be higher alphabetically.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws Exception {
        int result = 0;
        BufferedReader r = new BufferedReader(new InputStreamReader(System.in));

        String Diamonds = r.readLine();
        String Rocks = r.readLine();

        // No need to find somewhat in empty strings
        if (Diamonds.isEmpty() || Rocks.isEmpty()) {
            System.out.print(result);
            return;
        }

        // Make arrays of chars from strings
        char[] diamonds = Diamonds.toCharArray();
        char[] rocks = Rocks.toCharArray();

        // Sort arrays alphabetically
        Arrays.sort(diamonds);
        Arrays.sort(rocks);

        int start = 0;

        // Start iterate diamonds
        for(char diamond : diamonds){

         // For each diamond iterate rocks
         // but not from beginning,
         // start variable keeps last position
         // from previous iteration

            for(int i = start; i < rocks.length; i++){

                if(rocks[i] == diamond){
                    // Increment result 
                    // if found diamond in rock
                    result++;
                } else if(rocks[i] > diamond) {
                 // If rock is higher then diamond
                 // then go out from loop
                 // but save current position
                    start = i;
                    break;
                }
            }
        }

        System.out.print(result);
    }
}

In such way we iterate Rocks only once but not as many times as Diamonds exists when use brute force.