import java.util.Scanner;

/* This Java class has a method that, in effect, finds the k-th occurrence of
** a given character within a given String.  The purpose is to give students
** the opportunity to work with Java's assert statement and the loop invariant
** concept.
*/
public class FindKthOccurrence {

   /* Given String s (the "string of interest"), character x (the "character 
   ** of interest"), and integer k, returns the length of the shortest prefix 
   ** of s containing k occurrences of x.  (If there are fewer than k 
   ** occurrences of x in s, the value returned is -1.)
   **
   ** In other words, if s contains at least k occurrences of x, then the value
   ** returned is m, where position m-1 of s contains the k-th occurrence of x
   ** (making s.substring(0,m), abbreviated below as s[0..m), the shortest
   ** prefix of s containing k occurrences of x).
   **
   ** pre: k > 0
   */
   public static int findKth(String s, char x, int k) {
      int m = ??;    // missing initialization
      int occurCntr = ??;  // missing initialization

      assert loopInvariant(s, m, x, occurCntr);
      // loop invariant: s[0..m) (the prefix of s of length m) has 
      //                 exactly occurCntr occurrences of x
      while (??) {   // missing loop guard

         // missing loop body

         assert loopInvariant(s, m, x, occurCntr);
      }
      // loop postcondition: 
      //    EITHER occurCntr == k and s[0..m) is shortest prefix of s
      //           containing k occurrences of x
      //    OR occurCntr != k and s has fewer than k occurrences of x.
      //
      if (occurCntr != k) { return -1; }
      else { return m; }
   }

   /* Returns true iff s[0..m) (the prefix of s of length m) contains 
   ** exactly 'count' occurrences of x.
   */
   private static boolean loopInvariant(String str, int m, char x, int count) {
      for (int i=0; i != m; i++) {
         if (str.charAt(i) == x) 
            { count = count - 1; }
      }
      return count == 0;
   }

   /* A main() method whose purpose is to perform testing upon the findKth()
   ** method.  The user is invited to enter a "string of interest" and a
   ** "character of interest".  Making repeated use of findKth(), the
   ** program will report the shortest prefix of the string containing
   ** one occurrence of the character, two occurrences of the character,
   ** etc., etc., until it reaches the point where there are no more
   ** occurrences of that character in the string.
   */
   public static void main(String[] args) {
      System.out.println("Welcome to the Find K-th Occurrence Program.\n");
      Scanner input = new Scanner(System.in);
      System.out.print("Enter string of interest: ");
      String response = input.nextLine();
      System.out.print("Enter character of interest: ");
      char ch = input.nextLine().charAt(0); 
 
      int result;
      int k = 1;
      do {
         result = findKth(response, ch, k);
         if (result == -1) {
            System.out.printf("\"%s\" has fewer than %d occurrences of '%c'\n",
                              response, k, ch);
         }
         else {   
            System.out.printf("\"%s\" has %d occurrences of '%c'\n",
                             response.substring(0,result), k, ch);
            k = k+1;
         }
      } while (result != -1);

      System.out.println("\nGoodbye.");
   }

}