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 

@Absinthe

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;

Follow

Octave solution 

@khird so I d/l octave hopefully I will get to run some of your stuff soon

@Absinthe Great! I have been getting less interested in these without anybody giving me feedback.

Sign in to participate in the conversation
Qoto Mastodon

QOTO: Question Others to Teach Ourselves
An inclusive, Academic Freedom, instance
All cultures welcome.
Hate speech and harassment strictly forbidden.