It all depends on how you really want your algorithm to behave.
As an example, let us consider the string "a\u0308"
(U+0061 ʟᴀᴛɪɴ sᴍᴀʟʟ ʟᴇᴛᴛᴇʀ ᴀ followed by U+0308 ᴄᴏᴍʙɪɴɪɴɢ ᴅɪᴀᴇʀᴇsɪs), which is canonically equivalent to "ä"
or "\u00e4"
(U+00E4 ʟᴀᴛɪɴ sᴍᴀʟʟ ʟᴇᴛᴛᴇʀ ᴀ ᴡɪᴛʜ ᴅɪᴀᴇʀᴇsɪs). Being canonically equivalent means that your algorithm should not make a distinction between these two. One simple way to get canonically equivalent strings to behave the same is to normalize the two to the same canonical normalization form: either NFC or NFD.
Depending on what these strings represent, you may want to use compatibility equivalence (NFKC or NFKD) instead. That is generally recommended for, for example, identifiers. These two convert compatibility characters to their recommended equivalents (like U+2126 ᴏʜᴍ sɪɢɴ to U+03A9 ɢʀᴇᴇᴋ ᴄᴀᴘɪᴛᴀʟ ʟᴇᴛᴛᴇʀ ᴏᴍᴇɢᴀ, or ligature caracters to the sequences of characters they are made of).
Regardless of which kind of equivalence you want, the principle remains the same: if you want to treat equivalent strings equally normalizing both is the simplest way.
Once you have the same behaviour for all equivalent strings, you need to consider another issue: if you are discarding all "character[s] that [are]n't a letter or a digit", what happens with strings with letters and combining marks, like "\u092C\u093F"
(U+092C ᴅᴇᴠᴀɴᴀɢᴀʀɪ ʟᴇᴛᴛᴇʀ ʙᴀ followed by U+093F ᴅᴇᴠᴀɴᴀɢᴀʀɪ ᴠᴏᴡᴇʟ sɪɢɴ ɪ, looks like बि)? These are two separate codepoints, and U+093F is not a letter. These two do not compose in any normalization form. Do you want the combining marks to be dropped (leaving you with ब), or not?
If dropping them is fine, you can use your current algorithm. Otherwise, you probably want to iterate over grapheme clusters, which, put roughly, are sequences of base characters followed by the combining marks on it. Both Java and ICU provide APIs for finding grapheme clusters (Java calls these "character breaks").