The ultimate guide to coding interviews. Developed by FAANG engineers. Boost problem-solving skills with number theory, dynamic programming, and graph theory. Get interview-ready in just a few hours.

Competitive Programming - Crack Your Coding Interview.png

Whether you’re gearing up for online coding challenges, code-a-thons, or interviews, then this course is for you. With this course, you will solidify your problem-solving skills ensuring a swift sail through any problem. 


You will be tasked with solving some of the most frequently asked questions that are brought up in FAANG interviews. You will start with the concepts of Number Theory and Divide and Conquer, and gradually move towards more complex problems like dynamic programming and graph theory.


With each problem you solve, there will be insightful explanations and full implementation details to really hammer home the concepts. By the time you finish this course, you will have the confidence to solve any problem, no matter the difficulty.

Competitive Programming - Crack Your Coding Interview, C++

# Problem statement
**Given a sequence of characters, find the length of the longest palindromic subsequence in it.**

For example, if the given sequence is **BBABCBCAB**, the output should be **7** as **BABCBAB** is the longest
palindromic subsequence in it. A sequence is a palindromic sequence if that sequence reads the same backward as forwards, e.g. madam.
> Note: For the given sequence **BBABCBCAB**, subsequence **BBBBB** and **BBCBB** are also palindromic subsequences, but these are not the longest.

# Solution: **Recursive approach** 

The naive solution for this problem is to generate all subsequences of the given sequence and find the longest palindromic subsequence.

Let **X[0 .. n-1]** be the input sequence of length **n** and **L(0, n-1)** be the length of the longest palindromic subsequence of **X[0..n-1]**.

If the last and first characters of **X** are the same, then **L(0, n-1) = L(1, n-2) + 2**. Otherwise, **L(0, n-1) = MAX (L(1, n-1), L(0, n-2))**. 
So the recursive relation can be written as:

* Every single character is a palindrome of length 1 **L(i, i) = 1** for all indexes **i** in a given sequence.
* If the first and last characters are not same
   * If **X[i] != X[j]**, then **L(i, j) =  max{L(i + 1, j), L(i, j - 1)}** 
* If there are only 2 characters and both are the same
   * Else if **j == i + 1**, then **L(i, j) = 2**  
* If there are more than two characters, and the first and last characters are the same
   * Else **L(i, j) =  L(i + 1, j - 1) + 2**.

Let's move on to the implementation of this problem now.

Look at another commonly asked coding question based on strings and dynamic programming.

Overview

Number Theory

Number Theory

Divide and Conquer

Greedy Algorithms

Greedy Algorithms

Recursion and Backtracking

Recursion and Backtracking

Dynamic Programming

Graphs

Bonus Lessons

Longest Palindrome Subsequence

Problem statement