/*********************************************************************
* Author: Isai Damier
* Title: Find Unique characters
* Project: geekviewpoint
* Package: algorithms
*
* Statement:
* Given a text, assume ascii, find all the characters that appear
* in the text.
*
* Time Complexity: O(n)
*
* Sample Input: "Strike up, pipers!" Benedick's last words (Much Ado)
* Sample Output: {' ','!',',','S','e','i','k','p','r','s','t','u'}
*
* Technical Details:
*
* Even if you are given a 1000-page book, you may have the answer
* by the end of page one. If for instance the question is about the
* 26 letters of the English alphabet, all you need is a boolean
* array of size 26. Then as you read the book, each time you find
* a new character you mark it in the array and increment a counter.
* Once the counter reaches 26, you are done.
*
* If the text does not contain all the characters, then you do have
* to scan the whole text to find out. Then when you are done, you
* simple walk through the boolean vector and print the characters
* you did find.
********************************************************************/
public char[] uniqueChar(String s) {
/***
* create a bit vector of size 255; one entry for each possible
* characters
*/
final int ALL_CHARS = 255;
boolean usedChar[] = new boolean[ALL_CHARS];
int counter = 0;// char counter
for (char c : s.toCharArray()) {
if (!usedChar[(int) c]) {
usedChar[(int) c] = true;
counter++;
if (counter == ALL_CHARS) {
break;
}
}
}
char found[] = new char[counter];
for (int ndx = 0, i = 0; i < ALL_CHARS && ndx < counter; i++) {
if (usedChar[i]) {
found[ndx++] = (char) i;
}
}
return found;
}
package algorithms;
import org.junit.Test;
import static org.junit.Assert.*;
public class StringsTest {
public StringsTest() {
}
/**
* Test of uniqueChar method, of class Strings.
*
* Text from Macbeth: Malcolm speaking of Cawdor to Duncan
*/
@Test
public void testUniqueChar() {
System.out.println("uniqueChar");
String text = "My Liege, "
+ "They are not yet come back; but I have spoke "
+ "With one that saw him die: who did report, "
+ "That very frankly he confess'd his treasons, "
+ "Implor'd your Highness' pardon, and set forth "
+ "A deep repentance. Nothing in his life "
+ "Became him like the leaving it: he died "
+ "As one that had been studied in his death, "
+ "To throw away the dearest thing he ow'd, "
+ "As 'twere a careless trifle.";
Strings instance = new Strings();
char[] expResult = {' ', '\'', ',', '.', ':', ';', 'A', 'B', 'H',
'I', 'L', 'M', 'N', 'T', 'W', 'a', 'b', 'c', 'd',
'e', 'f', 'g', 'h', 'i', 'k', 'l', 'm', 'n',
'o', 'p', 'r', 's', 't', 'u', 'v', 'w', 'y'};
char[] result = instance.uniqueChar(text);
assertArrayEquals(expResult, result);
}
}