How to make memory constant (remove dependency on the number of unique characters)?

To make memory usage constant and remove dependence on the number of unique characters, techniques are usually used that do not store data directly for each unique character, but use fixed structures or algorithms with a constant amount of memory.

For example, if it is about counting character frequencies, instead of storing the frequency for each unique character, a fixed array can be used, whose size is equal to the maximum possible number of characters (for example, 256 for ASCII). Then, memory does not depend on the number of unique characters in a specific string, but is always constant.

In Go, this can be done as follows:

func countASCIIChars(s string) [256]int {
    var counts [256]int
    for i := 0; i < len(s); i++ {
        counts[s[i]]++
    }
    return counts
}

If the character set is larger (for example, Unicode), and you need to make memory constant, you can use hash functions with fixed-size tables or algorithms with a fixed amount of memory, such as counting with Bloom filters or other probabilistic data structures.

In summary: to remove dependence of memory on the number of unique characters, you need to use structures with a fixed size, known in advance and independent of input data.