# Problem: Shortest Common Supersequence Of Two Strings

## What is it?

Given two strings, `str1` and `str2`, find the shortest string that contains both `str1` and `str2` as subsequences.

> **Definition:** A string **S** is a subsequence of another string **T** if you can remove some characters from **T** (without changing the order of the remaining characters) to get **S**.

## Key Points

- The resulting string must include both input strings as subsequences.
- There may be more than one correct answer; any valid one is acceptable.
- A useful relation is:  
  **Length of SCS = len(str1) + len(str2) - len(LCS(str1, str2))**  
  where **LCS** stands for the longest common subsequence.

## Examples

### Example 1
**Input:**  
```
str1 = "abac"
str2 = "cab"
```

**Output:**  
```
"cabac"
```

**Explanation:**  
- `"abac"` is a subsequence of `"cabac"` (for example, remove the first `"c"`).
- `"cab"` is also a subsequence of `"cabac"` (for example, remove the last `"ac"`).

### Example 2
**Input:**  
```
str1 = "aaaaaaaa"
str2 = "aaaaaaaa"
```

**Output:**  
```
"aaaaaaaa"
```

**Explanation:**  
Both strings are identical; therefore, the SCS is the same as each string.

### Test Case 3
**Input:**  
```
str1 = "geek"
str2 = "eke"
```

**Possible Output:**  
```
"geeke"
```

**Explanation:**  
- `"geek"` is a subsequence of `"geeke"` (remove the extra `"e"` in the middle).
- `"eke"` is also a subsequence of `"geeke"`.

### Test Case 4
**Input:**  
```
str1 = "AGGTAB"
str2 = "GXTXAYB"
```

**Possible Output:**  
```
"AGGXTXAYB"
```

**Explanation:**  
The output `"AGXGTXAYB"` is one valid SCS that contains both `"AGGTAB"` and `"GXTXAYB"` as subsequences.

## Summary

1. **Understand subsequences:** Ensure both input strings appear in the output in the same order as they appear in the respective strings.
2. **Leverage the LCS:** The length of the SCS can be computed as:
   ```
   len(str1) + len(str2) - len(LCS(str1, str2))
   ```
3. **Return any valid SCS:** There may be several shortest common supersequences that satisfy the conditions.

## How the DP Array Is Useful

The **DP array** (or table) plays a crucial role in solving the Shortest Common Supersequence (SCS) problem by first helping us compute the **Longest Common Subsequence (LCS)** of the two input strings.

## Key Points
- **DP Array Construction:**
     - We create a 2D array `dp` with dimensions `(m+1) x (n+1)`, where `m` and `n` are the 
         lengths of the two strings.
     - `dp[i][j]` stores the length of the LCS between the first `i` characters of `str1` and the 
        first 
       `j` characters of `str2`.
- This is computed using the following rules:
    - If `str1[i-1] == str2[j-1]`, then `dp[i][j] = dp[i-1][j-1] + 1`.
    - Otherwise, `dp[i][j] = max(dp[i-1][j], dp[i][j-1])`.
- **Why LCS Matters:**
  - The LCS represents the sequence of characters common to both strings (in order) and helps us **identify overlapping parts**.
  - The formula `len(SCS) = len(str1) + len(str2) - len(LCS)` shows that the more characters the strings share (in order), the shorter the SCS can be.
  
- **Backtracking Using the DP Array:**
  - Once the DP array is filled, we **backtrack** from `dp[m][n]` to reconstruct the SCS.
  - **Backtracking Strategy:**
    - If the characters at `str1[i-1]` and `str2[j-1]` are the same, that character is part of the LCS, so we include it in the SCS and move diagonally (i.e., `i--, j--`).
    - If the characters differ, we compare `dp[i-1][j]` and `dp[i][j-1]`:
      - We move in the direction of the higher value, which means we are choosing the string that contributes more to the LCS.
    - After processing both strings, any remaining characters from either string are appended.
    - Since we construct the SCS in reverse order during backtracking, we reverse the result at the end.

## Summary

The DP array is useful because it:

1. **Stores Intermediate Results:** It calculates the LCS lengths for all possible prefixes, which is essential for determining where the two strings overlap.
2. **Guides the Reconstruction:** It helps decide which character to include next when building the SCS, ensuring that the order of characters is preserved.
3. **Minimizes Redundancy:** By using the LCS information, we avoid repeating common characters, thus ensuring the supersequence is as short as possible.

In essence, the DP array is the backbone of the solution—it not only provides the length of the LCS (which directly relates to the minimum SCS length) but also guides the process of merging the two strings into one minimal supersequence.


Feel free to use these examples to test and understand your solution!


Saurabh Patil

# Minimum Recolors to Get K Consecutive Black Blocks
**Difficulty:** Easy  
**Topics:** Strings, Sliding Window  

**Hint:** Use a sliding window to count the number of white blocks in every subarray of length `k` and find the minimum number to recolor.

---

## Problem Description

You are given a 0-indexed string `blocks` of length `n`, where `blocks[i]` is either `'W'` or `'B'`, representing the color of the `i`th block. The characters `'W'` and `'B'` denote the colors white and black, respectively.

You are also given an integer `k`, which is the desired number of consecutive black blocks.

In one operation, you can recolor a white block such that it becomes a black block.

Return the minimum number of operations needed such that there is at least one occurrence of `k` consecutive black blocks.

---

## Examples

### Test Case 1: Single Block (Needs Recoloring)
- **Input:** `blocks = "W"`, `k = 1`
- **Output:** `1`
- **Explanation:**  
  Only one block is available and it's white. It must be recolored to satisfy the requirement of 1 consecutive black block.

### Test Case 2: Single Block (Already Black)
- **Input:** `blocks = "B"`, `k = 1`
- **Output:** `0`
- **Explanation:**  
  The block is already black, so no recoloring is needed.

### Test Case 3: All Blocks White
- **Input:** `blocks = "WWWW"`, `k = 2`
- **Output:** `2`
- **Explanation:**  
  For any window of 2 blocks in a string of all white blocks, 0 black blocks exist. The optimal strategy is to recolor any two adjacent white blocks to get 2 consecutive black blocks.

### Test Case 4: Alternating Colors
- **Input:** `blocks = "BWBWBW"`, `k = 3`
- **Output:** `1`
- **Explanation:**  
  Consider the window starting at index 0: `"BWB"` contains 2 black blocks. Recoloring the white block in this window yields 3 consecutive black blocks.


## Constraints

- `n == blocks.length`
- `1 <= n <= 100`
- `blocks[i]` is either `'W'` or `'B'`.
- `1 <= k <= n`

---



# Count of Substrings Containing Every Vowel and K Consonants II

## Problem Statement
Given a string `word` and a non-negative integer `k`, return the total number of **substrings** of `word` that satisfy both of the following conditions:
- **Contain every vowel** ('a', 'e', 'i', 'o', and 'u') **at least once**.
- **Contain exactly `k` consonants**.

## Explanation
The task is to count all contiguous substrings of the input string `word` that:
- Include all the vowels: `a`, `e`, `i`, `o`, and `u`.
- Have **exactly** `k` consonants (letters that are not vowels).

## Constraints
- `5 <= word.length <= 2 * 10^5`
- `word` consists only of lowercase English letters.
- `0 <= k <= word.length - 5`

## Examples

### Example 1
- **Input:** `word = "cuaeio"`, `k = 1`
- **Explanation:**  
  The only valid substring is `"cuaeio"`. It contains all vowels (`u`, `a`, `e`, `i`, `o`) and exactly 1 consonant (`c`).
- **Output:** `1`

### Example 2
- **Input:** `word = "aeioubt"`, `k = 2`
- **Explanation:**  
  The substring `"aeioubt"` has all vowels and exactly 2 consonants (`b` and `t`). No other substring meets the criteria.
- **Output:** `1`

### Example 3
- **Input:** `word = "abaeiou"`, `k = 1`
- **Explanation:**  
  There are two valid substrings:
  - `"baeiou"` (from index 1 to 6) contains vowels (`a`, `e`, `i`, `o`, `u`) and 1 consonant (`b`).
  - `"abaeiou"` (from index 0 to 6) also contains all vowels and exactly 1 consonant (`b`).
- **Output:** `2`


## Constraints

-  $$ 5 <= word.length <= 2 * 10^5 $$
- `word` consists only of lowercase English letters.
- $$  0 <= k <= word.length - 5 $$



# Check if Grid can be Cut into Sections

## Problem Description
You are given an integer `n` representing the dimensions of an `n x n` grid, with the **origin at the bottom-left corner** of the grid. You are also given a **2D array of coordinates** `rectangles`, where `rectangles[i] = [startx, starty, endx, endy]` represents a rectangle on the grid. Each rectangle is defined as follows:

- `(startx, starty)`: The bottom-left corner of the rectangle.
- `(endx, endy)`: The top-right corner of the rectangle.

### **Conditions to Satisfy:**
Your task is to determine if **it is possible** to make either **two horizontal or two vertical cuts** on the grid such that:

1. Each of the **three resulting sections** formed by the cuts contains **at least one rectangle**.
2. Every rectangle belongs to **exactly one section** (i.e., no rectangle spans across a cut).

### **Return:**
- `true` if such cuts **can** be made.
- `false` otherwise.

---

## **Examples & Explanation**

### **Example 1**
#### **Input:**
```plaintext
n = 5
rectangles = [[1,0,5,2],[0,2,2,4],[3,2,5,3],[0,4,4,5]]
```
### Grid Representation:
![FDSSD](https://res.cloudinary.com/dluehhlfs/image/upload/v1742872550/GRIDCUT_gafd6a.png)

### Explanation:

We can make horizontal cuts at `y = 2` and `y = 4`, forming three sections:

- **Section 1:** Below `y = 2` (contains `R1`)
- **Section 2:** Between `y = 2` and `y = 4` (contains `R2` and `R3`)
- **Section 3:** Above `y = 4` (contains `R4`)

Since all conditions are satisfied, **output is `true`**.


## Constraints

$$
3 \leq n \leq 10^9
$$

$$
3 \leq \text{rectangles.length} \leq 10^5
$$

$$
0 \leq \text{rectangles}[i][0] < \text{rectangles}[i][2] \leq n
$$

$$
0 \leq \text{rectangles}[i][1] < \text{rectangles}[i][3] \leq n
$$

**Rectangles do not overlap.**



# Problem: Put Marbles in Bags

### Difficulty: `Hard`

### Problem Statement :

You have `k` bags and are given a 0-indexed integer array `weights` where `weights[i]` represents the weight of the `iᵗʰ` marble. Your task is to divide the marbles into the `k` bags following these rules:

1. **No bag is empty.**
2. **Contiguous Assignment:** If the `iᵗʰ` and `jᵗʰ` marbles are in a bag, then all marbles with indices between `i` and `j` must also be in that bag.
3. **Bag Cost:** If a bag contains marbles from index `i` to `j` inclusively, its cost is calculated as `weights[i] + weights[j]`.

The **score** after distributing the marbles is the sum of the costs of all `k` bags.

**Objective:** Return the difference between the maximum and minimum scores achievable through different valid distributions of the marbles.

### Examples

**Example 1:**


### ``Input:``  
```
weights = [1,3,5,1], k = 2
```
### `Output:` 
```
4
```

### `Explanation:`
- Minimal score distribution: [1], [3,5,1] → (1+1) + (3+1) = 6
- Maximal score distribution: [1,3], [5,1] → (1+3) + (5+1) = 10
Difference: 10 - 6 = 4

### ``Input:``
```  
weights = [1, 3], k = 2
```
### `Output:` 
```
0
```
### `Explanation:`
- The only possible distribution is [1], [3], resulting in the same score for both maximum and minimum.



# Topic: Factorials - A Breakdown and Recursive Approach  
**Difficulty:** Easy to Moderate  
**Topics:** Recursion, Iterative Algorithms, Mathematics  
**Applications:** Used in combinatorics, probability, and programming challenges.

---

## Concept of Factorials  
Imagine you have a set of building blocks, and you want to know how many unique structures you can create by stacking them in every possible arrangement. This is the idea behind factorials in mathematics.

### **Definition**  
The factorial of a number `n`, written as `n!` (n factorial), represents the total number of ways you can arrange a set of `n` distinct objects.

### **Example**  
For `n = 3` (3 blocks):  
$$
3! = 3 \times 2 \times 1 = 6 \text{ unique arrangements.}
$$
---

## Recursive Approach to Factorials  

### **What is Recursion?**  
Recursion involves solving a problem by breaking it down into smaller, similar subproblems. A **recursive function** calls itself within its body but with a smaller input until it reaches a **base case** (a condition where the function stops calling itself).

### **Factorial Using Recursion**  
To calculate `n!` using recursion:  
1. Multiply `n` by the factorial of `n-1`.  
2. Continue this process until `n` reaches the **base case**, where `n = 1` or `n = 0`.  

For these cases:  
$$
0! = 1 \quad \text{and} \quad 1! = 1.
$$

### **Recursive Formula**  
$$
n! = n \times (n-1)!
$$

---

## Example Walkthrough  
### Find `5!` Recursively:
1. `5! = 5 × 4!`  
2. `4! = 4 × 3!`  
3. `3! = 3 × 2!`  
4. `2! = 2 × 1!`  
5. `1! = 1` (Base case reached)  

**Result:**  
$$
5! = 5 \times 4 \times 3 \times 2 \times 1 = 120
$$

---


## Test Cases  

### Test Case 1: Small Number  
**Input:**  
`n = 5`  

**Execution:**  
`factorial_recursive(5)`  

**Output:**  
`120`  

---

### Test Case 2: Base Case (`n = 0`)  
**Input:**  
`n = 0`  

**Execution:**  
`factorial_recursive(0)`  

**Output:**  
`1`  

---

### Test Case 3: Base Case (`n = 1`)  
**Input:**  
`n = 1`  

**Execution:**  
`factorial_recursive(1)`  

**Output:**  
`1`  

---

### Test Case 4: Larger Number  
**Input:**  
`n = 10`  

**Execution:**  
`factorial_recursive(10)`  

**Output:**  
`3628800`  

---

# Count Good Triplets

**Difficulty:** Easy

**Topics:**  
*Array, Brute Force*



---

## Problem Statement

Given an array of integers `arr`, and three integers `a`, `b`, and `c`. You need to find the number of good triplets.

A triplet `(arr[i], arr[j], arr[k])` is **good** if the following conditions are true:
- `0 <= i < j < k < arr.length`
- `|arr[i] - arr[j]| <= a`
- `|arr[j] - arr[k]| <= b`
- `|arr[i] - arr[k]| <= c`

*Where `|x|` denotes the absolute value of `x`.*

Return the number of good triplets.

---

## Example 1

Input: ```arr = [3,0,1,1,9,7], a = 7, b = 2, c = 3```
Output: ```4```
Explanation: ```There are 4 good triplets: [(3,0,1), (3,0,1), (3,1,1), (0,1,1)].```


### Example 2


Input: ```arr = [1,1,2,2,3], a = 0, b = 0, c = 1```
Output: ```0```
Explanation: ```No triplet satisfies all conditions.```




### Constraints

$$
3 \le \text{arr.length} \le 100
$$

$$
0 \le \text{arr}[i] \le 1000
$$

$$
0 \le a,\, b,\, c \le 1000
$$



#  Count Good Triplets in an Array

**Difficulty:** Hard

**Topics:**  
*Array , Binary Search , Binary Indexed Tree , Divide and Conquer , Merge Sort , Ordered Set , Segment Tree*




**Hint:**  
You are given two 0-indexed arrays `nums1` and `nums2` of length `n`, both of which are permutations of `[0, 1, ..., n - 1]`.

A **good triplet** is a set of 3 distinct values which are present in increasing order by position both in `nums1` and `nums2`. In other words, if we consider `pos1v` as the index of the value `v` in `nums1` and `pos2v` as the index of the value `v` in `nums2`, then a good triplet will be a set `(x, y, z)` where `0 <= x, y, z <= n - 1`, such that `pos1x < pos1y < pos1z` and `pos2x < pos2y < pos2z`.

Return the total number of good triplets.

---

## Example 1

Input: ```nums1 = [2,0,1,3], nums2 = [0,1,2,3]```
Output: ```1```
Explanation: 
```There are 4 triplets (x, y, z) such that pos1x < pos1y < pos1z. They are (2,0,1), (2,0,3), (2,1,3), and (0,1,3).```
```Out of those triplets, only the triplet (0,1,3) satisfies pos2x < pos2y < pos2z. Hence, there is only 1 good triplet.```

## Example 2
Input: ```nums1 = [4,0,1,3,2], nums2 = [4,1,0,2,3]```
Output: ```4```
Explanation: ```The 4 good triplets are (4,0,3), (4,0,2), (4,1,3), and (4,1,2).```


### Constraints

-    $$ n = \text{nums1.length} = \text{nums2.length}$$
-  $$ 3 \le n \le 10^5 $$
- $$ 0 \le \text{nums1}[i], \ \text{nums2}[i] \le n - 1$$
- $$ \text{nums1 and nums2 are permutations of } \{ 0, 1, \dots, n - 1 \} $$


Select a card whose code you want to track