CC-9 : Check if characters of the String are well spaced.

Description:

Given an input String str and integer array spaces of size 26, where str contains only lowercase letters and each lowercase character is contained twice only, and spaces[i] contains the distance between the duplicate chars of str. Check if the characters in str are wellspaced.

Test cases and expected outputs:

Input Parameters	Expected outputs
str="rccrvabvba"; The spaces array is: [0] = 3 [1] = 1 [2] = 0 [3] = 0 [4] = 0 [5] = 0 [6] = 0 [7] = 0 [8] = 0 [9] = 0 [10] = 0 [11] = 0 [12] = 0 [13] = 0 [14] = 0 [15] = 0 [16] = 0 [17] = 2 [18] = 0 [19] = 0 [20] = 0 [21] = 2 [22] = 0 [23] = 0 [24] = 0 [25] = 0	The array is well spaced.
str="aceace"; The spaces array is: [0] = 3 [1] = 1 [2] = 0 [3] = 0 [4] = 0 [5] = 0 [6] = 0 [7] = 0 [8] = 0 [9] = 0 [10] = 0 [11] = 0 [12] = 0 [13] = 0 [14] = 0 [15] = 0 [16] = 0 [17] = 2 [18] = 0 [19] = 0 [20] = 0 [21] = 2 [22] = 0 [23] = 0 [24] = 0 [25] = 0	The array is not well spaced.

Input Parameters

Expected outputs

str="rccrvabvba";

The spaces array is:  
[0] = 3
[1] = 1
[2] = 0
[3] = 0
[4] = 0
[5] = 0
[6] = 0
[7] = 0
[8] = 0
[9] = 0
[10] = 0
[11] = 0
[12] = 0
[13] = 0
[14] = 0
[15] = 0
[16] = 0
[17] = 2
[18] = 0
[19] = 0
[20] = 0
[21] = 2
[22] = 0
[23] = 0
[24] = 0
[25] = 0

The array is well spaced.

str="aceace"; The spaces array is:

[0] = 3
[1] = 1
[2] = 0
[3] = 0
[4] = 0
[5] = 0
[6] = 0
[7] = 0
[8] = 0
[9] = 0
[10] = 0
[11] = 0
[12] = 0
[13] = 0
[14] = 0
[15] = 0
[16] = 0
[17] = 2
[18] = 0
[19] = 0
[20] = 0
[21] = 2
[22] = 0
[23] = 0
[24] = 0
[25] = 0

The array is *not* well spaced.

Pseudocode:

The java method should accept following input parameters: str (String), spaces (Integer array).

Initialize a variable strDistMap of type HashMap to hold characters from str and distances from their next occurrence.

Initialize c to a blank character. Initialize chrSpace to 0. Initialize spacesIdx to 0.

Iterate through str using a for loop with idx as a loop variable with initial value 0 and increment idx till it reaches str.length()-1:

Initialize c to str.charAt[idx).

Initialize chrSpace to 0.

If strDistMap does not contain key c:

Add key str.charAt(idx)and add value idx to strDistMap.

If strDistMap contains key equal to c:

Set chrSpace to (idx- strDistMap.get( c )-1). This gives us distances between c and its duplicate character in str.

Set spacesIdx to (c-a). This gives us the index of c in spaces.

If chrSpace is not equal to spacesIdx, the current character c and its duplicate are not well spaced, so return false from the program.

If the above loop completes successfully without returning false from the program, that means the character in str are well spaced, so return true.

Code:

public boolean hashMapChkWellSpaced(String str, int[] spaces) throws Exception{
	HashMap<Character,Integer> strDistMap=new HashMap<Character, Integer>();
	char c='\u0020'; int chrSpace=0; int spacesIdx=0;
	for (int idx=0; idx < str.length(); idx++) {
		c=str.charAt(idx);
		if (strDistMap.get(c)==null) {
			strDistMap.put(str.charAt(idx), idx);
		}else {
			chrSpace=idx-strDistMap.get(c)-1;
			strDistMap.put(str.charAt(idx), chrSpace);
			spacesIdx=c-'a';
			if (chrSpace != spaces[spacesIdx]) {
				System.out.println("\n\n*Not* well spaced for "+c);
				return false;
			}
		}
	}
	return true;		
}

Click here to download and run code and test cases !

Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it. Be sure to try your own test cases to enhance your understanding ! You can also tweak the code to optimize or add enhancements and custom features.

import java.util.HashMap;


public class HashMapChkWellSpaced {
	
public boolean hashMapChkWellSpaced(String str, int[] spaces) throws Exception{
	HashMap<Character,Integer> strDistMap=new HashMap<Character, Integer>();
	char c='\u0020'; int chrSpace=0; int spacesIdx=0;
	for (int idx=0; idx < str.length(); idx++) {
		c=str.charAt(idx);
		if (strDistMap.get(c)==null) {
			strDistMap.put(str.charAt(idx), idx);
		}else {
			chrSpace=idx-strDistMap.get(c)-1;
			strDistMap.put(str.charAt(idx), chrSpace);
			spacesIdx=c-'a';
			if (chrSpace != spaces[spacesIdx]) {
				System.out.println("\n\n*Not* well spaced for "+c);
				return false;
			}
		}
	}
	return true;		
}
	
	
    
public static void main(String[] args) {
		
	HashMapChkWellSpaced hp=new HashMapChkWellSpaced();
	boolean retVal;
	try {
	String str1="rccrvabvba";
	int[] spaces= {
					3, //a
					1, //b
					0, //c
					0, //d
					0, //e
					0, //f
					0, //g
					0, //h
					0, //i
					0, //j
					0, //k
					0, //l
					0, //m
					0, //n
					0, //o
					0, //p
					0, //q
					2, //r
					0, //s
					0, //t
					0, //u
					2, //v
					0, //w
					0, //x
					0, //y
					0, //z					
		};
	System.out.println("\n\nThe String is: "+str1);
	printArray(spaces, "The spaces array is: ");
	retVal=hp.hashMapChkWellSpaced(str1, spaces);
	if (retVal==true) {
		System.out.println("\n The array is well spaced");
	}else {
			System.out.println("\n The array is *not* well spaced");
	}
			
			
	str1="cvbfvdecbfde";
	int[] spaces1= {
					0, //a
					5, //b
					6, //c
					4, //d
					4, //e
					5, //f
					0, //g
					0, //h
					0, //i
					0, //j
					0, //k
					0, //l
					0, //m
					0, //n
					0, //o
					0, //p
					0, //q
					0, //r
					0, //s
					0, //t
					0, //u
					2, //v
					0, //w
					0, //x
					0, //y
					0, //z					
			};
	System.out.println("\n\nThe String is: "+str1);
	printArray(spaces, "The spaces array is: ");
	retVal=hp.hashMapChkWellSpaced(str1, spaces1);
	if (retVal==true) {
		System.out.println("\n The array is well spaced");
	}else {
		System.out.println("\n The array is *not* well spaced");
	}
			
	str1="aceace";
	int[] spaces2= {
					2, //a
					0, //b
					2, //c
					0, //d
					3, //e
					0, //f
					0, //g
					0, //h
					0, //i
					0, //j
					0, //k
					0, //l
					0, //m
					0, //n
					0, //o
					0, //p
					0, //q
					0, //r
					0, //s
					0, //t
					0, //u
					0, //v
					0, //w
					0, //x
					0, //y
					0, //z					
	};
	System.out.println("\n\nThe String is: "+str1);
	printArray(spaces, "The spaces array is: ");
	retVal=hp.hashMapChkWellSpaced(str1, spaces2);
	if (retVal==true) {
			System.out.println("\n The array is well spaced");
	}else {
		System.out.println("\n The array is *not* well spaced");
	}
						
						
	}catch (Exception exception) {
		System.out.print("Exception: "+ exception);
	}
				
}

public static void printArray(int[] intArray, String label) throws Exception {
	// Case 1: The input Array is null !!
	if (intArray == null) { System.out.println("\n\n Input Array was null !! \n"); return; }
	// Case 2: Print input Array by index (first to last)
	System.out.println();
	System.out.println("**********************************************************************");
	System.out.print(label+" : \n");
	int arrayIndex=0;
	for (arrayIndex=0; arrayIndex < intArray.length; arrayIndex++) {
			System.out.print("["+arrayIndex+"] = "+intArray[arrayIndex]+"\n");
	} 
	System.out.println();
	System.out.println("**********************************************************************");
	System.out.println();
	Thread.sleep(2000);
	return;
}

}