SDE - Intern

Step 1: Initially, I thought of generating all substrings and checking uniqueness using a set, but that leads to O(n³) complexity.
Step 2: Then I optimized using the sliding window technique with two pointers.
Step 3: Used a hash set/map to track characters and expanded the window until a duplicate appears.
Step 4: When a duplicate is found, shrink the window from the left until it becomes valid again.
Step 5: Keep updating the maximum length during traversal.

Step 1: Initially thought of checking all paths, but that is exponential.
Step 2: Used recursion with DFS to compute maximum gain from each node.
Step 3: For each node, calculate left and right subtree contributions (ignore negatives).
Step 4: Update global maximum as left + right + node value.
Step 5: Return max gain to parent as node + max(left, right).

Step 1: Started with a recursive solution comparing characters, but it led to overlapping subproblems (exponential time).
Step 2: Introduced memoization to store results of subproblems.
Step 3: Converted to bottom-up DP using a 2D table.
Step 4: If characters match → dp[i][j] = 1 + dp[i-1][j-1]
Step 5: Else → dp[i][j] = max(dp[i-1][j], dp[i][j-1])
Step 6: Final answer stored in dp[n][m].