// Arup Guha
// 4/27/2019
// Solution to 2017 AP CS FR Question #3: Phrase

import java.util.*;

public class Phrase {

	private String currentPhrase;
	
	public Phrase(String p) {
		currentPhrase = p;
	}
	
	public String toString() {
		return currentPhrase;
	}
	
	// This is my implementation...I don't allow two occurrences of str to overlap...
	public int findNthOccurrence(String str, int n) {
		
		// Don't destroy currentPhrase.
		String tmp = currentPhrase;
		int idx = 0;
		
		// Try n times.
		for (int i=0; i<n; i++) {
			
			// Here is my hop in tmp.
			int hop = tmp.indexOf(str);
			
			// n occurrences don't exist.
			if (hop == -1) return -1;
			
			// Chop my string and chop the current copy of str as well.
			tmp = tmp.substring(hop+str.length());
			
			// This is the hop length.
			idx += hop;
			
			// For every hop but the first, we also hop the previous string length...
			if (i > 0) idx += str.length();
		}
		
		// Ta da!
		return idx;
	}
	
	public void replaceNthOccurrence(String str, int n, String repl) {
		
		// Find the location of the nth occurrence.
		int idx = findNthOccurrence(str, n);
		if (idx == -1) return;
		
		// Just slice and put back together!
		currentPhrase = currentPhrase.substring(0, idx) + repl + currentPhrase.substring(idx+str.length());
	}
	
	public int findLastOccurrence(String str) {
		
		// No occurrences exist.
		int res = findNthOccurrence(str, 1);
		if (res == -1) return -1;
		
		// Let's try to find more occurrences...
		int idx = 2;
		while (res != -1) {
			
			// This is the next one.
			int tmp = findNthOccurrence(str, idx);
			
			// There isn't a next one, so the previous one was the last.
			if (tmp == -1) return res;
			
			// We can safely update res and idx.
			res = tmp;
			idx++;
		}
		
		// Will never get here but Java gets annoyed without this.
		return -1;
	}
	
	public static void main(String[] args) {
		
		// Just some of my tests.
		Phrase p = new Phrase("how are you doing you or you or you or you or you??? or you man?");
		p.replaceNthOccurrence("you", 5, "me, me, me!");
		System.out.println(p);
		System.out.println("Location of last you is "+p.findLastOccurrence("you"));
		System.out.println("Location of last occurrence of when is "+p.findLastOccurrence("when"));
		System.out.println("Location of last occurrence of man. is "+p.findLastOccurrence("man."));
	}

}