First, there was an online coding round consisting of two DSA questions. After clearing that, I had two technical interview rounds scheduled.

In the second round, I was asked two DSA problems – both based on Dynamic Programming – along with a few questions related to Amazon’s Leadership Principles.

In the third technical round, the interviewer gave me one coding problem and asked me to explain my approach step-by-step, starting from the brute force solution to the optimized version. They also discussed a few Leadership Principles.

The fourth round was a managerial interview, where I was asked about my previous work experience, one string-based coding question, and additional questions related to Leadership Principles.

Can you first explain your brute-force solution, and then optimize it step by step while discussing the time and space complexity?