Average case algorithm analysis using Kolmogorov Incompressibility Method
The idea of the incompressibility method is that an incompressible input satisfies certain properties that can be helpful in the analysis. In your case, the complexity of the algorithm depends on how many characters appear in the string. When processing the $k$th character, the "running time" (or rather its proxy, the number of comparisons when checking the list) is $\approx \alpha_k/2$ comparisons on average, where $\alpha_k$ is the number of different characters that have been seen so far. In order to estimate $\alpha_k$, note that we can encode the first $k$ characters using roughly $8\alpha_k + k\log \alpha_k$ bits, and we deduce that $8\alpha_k + k\log_2 \alpha_k \geq 8k$. Hence unless $k$ is very small, $\alpha_k$ has to be very close to $256$, and we can deduce that there are on average $128$ comparisons per character. We can use the inequality to determine how large $k$ needs to be, and also what happens when $k$ is small.

The reason we are trying to count the exact complexity in the case of your algorithm is that its worst-case and best-case running times are both $\Theta(n)$. We used incompressibility to estimate $\alpha_k$, which can also be estimated directly using probabilistic methods, but the incompressibility calculation is probably simpler. Still, incompressibility doesn't obviate the need to analyze the algorithm probabilistically – it just makes the analysis more tractable in some cases.