The ultimate guide to dynamic programming interviews in C++ with strategies developed by FAANG engineers. Practice with real-world questions and get interview-ready in just a few hours.

Some of the toughest questions in technical interviews require dynamic programming solutions. Dynamic programming (DP) is an advanced optimization technique applied to recursive solutions. However, DP is not a one-size-fits-all technique, and it requires practice to develop the ability to identify the underlying DP patterns. With a strategic approach, coding interview prep for DP problems shouldn’t take more than a few weeks.

This course starts with an introduction to DP and thoroughly discusses five DP patterns. You’ll learn to apply each pattern to several related problems, with a visual representation of the working of the pattern, and learn to appreciate the advantages of DP solutions over naive solutions.

After completing this course, you will have the skills you need to unlock even the most challenging questions, grok the coding interview, and level up your career with confidence.

This course is also available in JavaScript, Python, and Java—with more coming soon!

Grokking Dynamic Programming Interview in C++

# Statement
Given a string, you have to find the length of the longest subsequence that occurs at least twice and respects this constraint: the characters that are re-used in each subsequence should have distinct indexes.

> **Note:** A subsequence is part of an array whose elements are not necessarily contiguous. For example, given an array "_abcde_", both "_abcd_" and "_abe_" are subsequences of the original array.

For example, let’s say you have to find the longest repeating subsequence from the string "_aaaaba_". In this string, the longest repeating subsequence will be of length $4$ because the subsequence "_aaaa_" occurs twice.

Subsequence 1 = "_aaaa_" (indexes: 0, 1, 2, 3)

Subsequence 2 = "_aaaa_" (indexes: 1, 2, 3, 5)

Observing both subsequences, we note that the "a"'s at indexes $1$, $2$, and $3$ occur in both subsequences. However, we must understand that although they are repeating, the placement of these “a”'s is different in each subsequence. In the first subsequence, the "a" at index $1$ in the original string is placed at index $1$, while in the second subsequence, it is placed at the $0th$ index.

**Constraints:**
* $0 \leq$ `str.length` $\leq 1300$

# Examples

Let's solve the Longest Repeating Subsequence using Dynamic Programming.

Getting Started

0/1 Knapsack

Unbounded Knapsack

Recursive Numbers

Longest Common Substring

Palindromic Subsequence

Conclusion

Longest Repeating Subsequence