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 two strings `str1` and `str2`, return the shortest string (supersequence) that has both `str1` and `str2` as subsequences.  If multiple answers exist, you may return any of them.**

> *A string S is a subsequence of string T if deleting some number of characters from T (possibly 0, and the characters are chosen anywhere from T) results in the string S.*

Let's look at the following example:

* We have two strings, **str1 = apple** and **str2 = les**. The SCS of both the strings will be **apples** as it contains both the strings as a subsequence.

* We have two strings, **str1 = AGGTAB** and **str2 = GXTXAYB**. The SCS of both the strings will be **AGGXTXAYB** as it contains both the strings as a subsequence.

# Solution: **Dynamic programming approach**
This problem is somewhat close to Longest Common Subsequence. We will use the following approach to solve this problem:

* First, we will find the LCS of the two strings.
* Then, we will insert the non-LCS characters in the LCS found above in their original order.

Let us consider our previous example, **str1 = AGGTAB** and **str2 = GXTXAYB**. LCS of **str1** and **str2** is **GTAB**. Once we find LCS, we insert characters of both strings in order and we get **AGXGTXAYB**.

This problem is one of the most asked problems in coding interviews. 

Let's move to the implementation now.

Take your dynamic programming skills to the next level by solving this string-based problem.

Overview

Number Theory

Number Theory

Divide and Conquer

Greedy Algorithms

Greedy Algorithms

Recursion and Backtracking

Recursion and Backtracking

Dynamic Programming

Graphs

Bonus Lessons

Shortest Common Supersequence of Two Strings

Problem statement