Amazon Interview Question

Given a string containing alphanumeric characters, write a function to find the longest substring with at most K distinct characters. If multiple substrings of the same length exist, return the first one found. Optimize the solution for both time and space complexity.