Here's another freebie:
This problem was asked by Amazon.
Given an integer k and a string s, find the length of the longest substring that contains at most k distinct characters.
For example, given s = "abcba" and k = 2, the longest substring with k distinct characters is "bcb".
Octave solution
Space linear in k, time linear in k*|s|.
function string_size = uniform_substring(alphabet_size, base_string)
string_size = 0;
string_start = 0;
recent_letters = zeros(alphabet_size, 1);
recent_indices = zeros(alphabet_size, 1);
for index = 1:numel(base_string)
cache = find(recent_letters == base_string(index) & recent_indices ~= 0, 1);
if isempty(cache)
cache = find(recent_indices == 0, 1); end;
if isempty(cache)
[~, cache] = min(recent_indices);
string_size = max(string_size, index - string_start - 1);
string_start = recent_indices(cache); end;
recent_letters(cache) = base_string(index);
recent_indices(cache) = index;
end;
string_size = max(string_size, numel(base_string) - string_start); end;
@Absinthe Great! I have been getting less interested in these without anybody giving me feedback.