Solve common string/DP/stack problems
Quick Overview
This set of four coding tasks evaluates proficiency in string algorithms, dynamic programming, sliding-window techniques, monotonic stack usage, and time/space complexity analysis.
You are given four independent coding tasks. For each task, describe your approach and analyze time and space complexity.
Task 1: Longest substring with all distinct characters
Input: A string s (ASCII or lowercase letters).
Output: An integer = the maximum length of a contiguous substring of s that contains no repeated characters.
Example: s = "abcabcbb" → output 3 (e.g., "abc").
Constraints (typical): 0 ≤ |s| ≤ 2e5.
Task 2: Largest rectangle in a histogram
Input: An array heights of length n, where heights[i] is the height of the i-th bar in a histogram. Each bar has width 1.
Output: The maximum area of any axis-aligned rectangle that can be formed using one or more contiguous bars.
Example: heights = [2,1,5,6,2,3] → output 10 (bars 5 and 6).
Constraints (typical): 1 ≤ n ≤ 2e5, 0 ≤ heights[i] ≤ 1e9.
Task 3: Minimum cost to reach the last index with 1–2 steps
You start at index 0. From index i, you may move to i+1 or i+2 (if within bounds). Visiting an index i incurs cost[i] (including index 0 and the last index).
Input: Arrays cost (or nums + per-position cost) of length n.
Output: The minimum total cost to reach index n-1.
Example: cost = [1,100,1,1,1,100,1,1,100,1] → output 6.
Constraints (typical): 1 ≤ n ≤ 2e5, 0 ≤ cost[i] ≤ 1e9.
Task 4: Longest palindromic substring
Input: A string s.
Output: A substring of s that is a palindrome and has maximum possible length. If multiple answers exist, return any one.
Example: s = "babad" → output "bab" (or "aba").
Constraints (typical): 1 ≤ |s| ≤ 2e3 (or specify if larger and discuss tradeoffs).