Question (in Chinese): http://ac.jobdu.com/problem.php?pid=1283
Question Name: First No Repeating Char
Question Description: Given a string with only upper-case letters, find the first non-repeating char.
Input: the input might contain multiple test cases. Each line is a test case. Only upper-case letters are used in the test cases.
Output: If there is a non-repeating char, print its index; otherwise, print “-1”.
1 2 3 4 5 6 7 8 | Input: ABACCDEFF AA AAB Output: 1 -1 2 |
The solution is:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 | /*---------------------------------------------------------------- * Author: Sheng Yu - codesays.com * Written: 09/01/2014 * Last updated: 09/01/2014 * * Filename: FirstNoRepeatingChar.java * Compilation: javac FirstNoRepeatingChar.java * Execution: java FirstNoRepeatingChar * JDK Used: 1.7 *----------------------------------------------------------------*/ import java.util.Scanner; /** * An utility to find the first no-repeating char in a given string. * @author Sheng Yu - codesays.com */ public class FirstNoRepeatingChar { /** * Find the first no-repeating char in a given string. * @param input the original string to find the no-repeating char. * @return the index of the first no-repeating char. */ public int findNoRepeatingChar(String input) { int[] counter = new int[26]; int[] lastIndex = new int[26]; // Count the occurrence of the upper case letters, and the index // of their last occurrence. If it only appears once, the last // occurrence is also the first occurrence. int pos = 0; for (int i = 0; i < input.length(); ++i) { // 65 is the ASICC value of "A" pos = (int) input.charAt(i) - 65; counter[pos] += 1; lastIndex[pos] = i; } // Find the first no-repeating char. int first = input.length(); for (int i = 0; i < counter.length; ++i) { if (counter[i] == 1 && lastIndex[i] < first) { first = lastIndex[i]; } } return first == input.length() ? -1 : first; } /** * Stub for test. * @param args the command line arguments. */ public static void main(String[] args) { Scanner in = new Scanner(System.in); FirstNoRepeatingChar finder = new FirstNoRepeatingChar(); while (in.hasNextLine()) { System.out.println(finder.findNoRepeatingChar(in.nextLine())); } } } |