Google Onsite 2020 pt2

// input: 2 strings target and lyrics
// output: boolean if target shows up in lyrics, s.t. each target char only appears once in a word
// case insensitive
/**

Example1)
target = "boots"
lyrics = "baby 
		close them 
		doors and 
		turn them 
		lights down low."

true

Example2)
target = ""
lyrics = "And I was like baby, baby, baby, ohh"

false

Example3)
target = "boots"
lyrics = "What"

false
*/

TARGET CHARS: N
LYRICS CHARS: M

public boolean findTargetInLyrics(String target, String lyrics) {
	int targetPtr = 0, lyricsPtr = 0;
	String[] lyricsArr = lyrics.split(" ");

	// base cases
	if (target.isEmpty() && lyrics.isEmpty()){
		reutrn true;
	} else if (target.isEmpty() || lyrics.isEmpty() || target.size > lyricsArr.length) {
		return false;
	}

	while (targetPtr < target.size() && lyricsPtr < lyricsArr.length) {
		Character targetChar = target.charAt(targetPtr); // t
		String lyricWord = lyricsArr[lyricsPtr]; // and
		for (int i=0; i<lyricWord.size(); i++) {
			if (targetChar == lyricWord.charAt(i)) { // o matches
				targetPtr++; // 3
				break;
			}
		}

		// didn't find a match or found a match, always increment lyricsPtr
		lyricsPtr++; // 4
	}

	return (targetPtr == target.size());
}

Time Complexity: O(N+M)
Space Complexity: O(M)