Longest Substring and LRU Cache

MediumPython

Problem

The Allstate Claims experience processes session text and repeatedly accesses recently used session values. Implement both of the following algorithms:

Find the length of the longest substring without repeating characters.
Design an LRU cache supporting get and put in O(1) average time.

Create a solve function that returns the substring result and executes a sequence of cache operations. A cache get returns the stored value or -1 when the key is absent. A successful get, and every put, marks the key as most recently used. When capacity is exceeded, evict the least recently used key.

Formal Specification

s is a string and may contain any Python characters.
capacity is a positive integer.
operations is a list of lists. Each operation is either ['put', key, value] or ['get', key], where keys and values are integers.
Return a dictionary with longest_length, an integer, and cache_results, a list containing the result of each get operation in order.

Constraints

0 <= len(s) <= 10^5
1 <= capacity <= 10^4
0 <= len(operations) <= 10^5
Each operation is either ['put', key, value] or ['get', key]
Keys and values are integers

Function Signature

def solve(s, capacity, operations):

The Allstate Claims experience processes session text and repeatedly accesses recently used session values. Implement both of the following algorithms:

Find the length of the longest substring without repeating characters.
Design an LRU cache supporting get and put in O(1) average time.

Formal Specification

s is a string and may contain any Python characters.
capacity is a positive integer.
operations is a list of lists. Each operation is either ['put', key, value] or ['get', key], where keys and values are integers.
Return a dictionary with longest_length, an integer, and cache_results, a list containing the result of each get operation in order.