So my friend gave me a challenge for TI-Basic coding. Basically you are given a string and have to test it if there are any repeating letters. For example, the string "SILVER" would pass, but the string "YELLOW" would not because there are 2 L's.

I'm having a ton of trouble trying to think this out, and my friend said that since he didn't know how to do it either after we both spent a week thinking that I should just ask on Cemetech. So here I am.

This algorithm is needed to make a custom Caesar cipher (link leads to Wikipedia) program that my friend and I have been working on together.

Any help is appreciated.

There are a bunch of clever things you can do here, that I can think of. I have them listed from the most naive (worst and least efficient) to the most efficient.
1) Most naive: iterate through the string 26 (or more) times, counting letters each time, and looking for a sum above 1. This might be described as O(n), although it has a constant cost coefficient of 26 (ie, O(26n). This might look like this:
Code:

2) The first optimization would be to stop immediately when you see a repeat of a letter:
Code:

3) The next optimization would be, instead of checking if every letter is the one you want, to use inString() to determine the next position of each letter. This makes it a faster O(mn) algorithm, but still essentially O(n):
Code:

4) Here's where the algorithm suddenly gets clever. Instead of searching for all possible letters, we simply search for repeated instances of each letter in the string. This way, we don't have to specify the exact set of allowed characters, and we save scanning over any characters that don't exist in the string:
Code:


Please ask any and all questions you have on how I refined the algorithm and how that final version works.

Dude, Kerm you are amazing.

This just made my life a lot easier. Thanks a million for your help, I was expecting some long-winded line of code that would use up several hundred bytes of memory but your code (particularly the most efficient one) is great.

Kerm++ for that. Very nice explanation. If you really wanted to, you could make it in one line, but Kerm's works well in that you don't have to check every character. Here's another way:

Code:

It basically just replaces the for loop with the seq() command. If it is true, then there are repeated letters.

Also, as a side thing, if you want to check if two consecutive letters are the same, you could modify it like this:

Code:


Hope that your cipher program goes well!

Mateo: Very true. I considered using a seq() construction to eliminate the loop, but the downsides are (1) a bigger memory footprint (the temporary list of magnitude |set(unique_letters_in_string)| and (2) more computation when a duplicate appears, since it has to run the entire "loop" instead of being able to short-circuit out.