Editorial for UHCC1 P2 - String - Olympiads Online Judge

Editorial for UHCC1 P2 - String

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: noirsnow

This problem can be solved using brute-force. More specifically, construct an empty list filled with zeros of length $K$ ~K~, with position $i$ ~i~ representing the appearance count of the $i^{th}$ ~i^{th}~ character in $S$ ~S~. Iterate over all $N$ ~N~ words and add ones to positions in the list representing its appearance wherever the word appears in $S$ ~S~. The answer is the number of characters that have a count greater than 1 in the list.

Worst Case Time Complexity: $\mathcal{O}(KM)$ ~\mathcal{O}(KM)~ when there are many occurrences of the $N$ ~N~ words in $S$ ~S~, where $M$ ~M~ is the total characters of the $N$ ~N~ words.

Comments

There are no comments at the moment.