Unique Substrings in Wraparound String
Given a string p, find the number of unique non-empty substrings of p that are also substrings of the infinite wraparound string "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz...". The infinite string repeats the alphabet sequence cyclically.
DP Solution: We'll use a DP array where dp[i] represents the length of the longest valid substring ending at position i. We'll then use a hash array to track the maximum length for each ending character to avoid counting duplicates.
class Solution {
public:
int findSubstringInWraproundString(string s)
{
int n = s.size();
vector<int> longest(n, 1);
for (int i = 1; i < n; i++) {
bool isConsecutive = (s[i-1] + 1 == s[i]) ||
(s[i-1] == 'z' && s[i] == 'a');
if (isConsecutive) {
longest[i] = longest[i-1] + 1;
}
}
int maxLen[26] = {0};
for (int i = 0; i < n; i++) {
int idx = s[i] - 'a';
maxLen[idx] = max(maxLen[idx], longest[i]);
}
int total = 0;
for (int i = 0; i < 26; i++) {
total += maxLen[i];
}
return total;
}
};
Longest Increasing Subsequence
Given an integer array nums, return the length of the longest strictly increasing subsequence. A subsequence is a sequence that can be derived from the array by deleting some or no elements without changing the order.
DP Solution: We'll use dp[i] to store the length of the longest increasing subsequence ending at position i. For each position, we check all previous positions to find the best extension point.
class Solution {
public:
int lengthOfLIS(vector<int>& arr)
{
int n = arr.size();
vector<int> subseqLen(n, 1);
int maxLen = 1;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (arr[i] > arr[j]) {
subseqLen[i] = max(subseqLen[i], subseqLen[j] + 1);
}
}
maxLen = max(maxLen, subseqLen[i]);
}
return maxLen;
}
};
Wiggle Subsequence
A wiggle sequence is defined as a sequence where the differences between successive numbers strictly alternate between positive and negative. Given an integer array nums, return the length of the longest wiggle subsequence.
DP Solution: We need two DP arrays - one for subsequences ending with an upward difference and another for those ending with a downward difference.
class Solution {
public:
int wiggleMaxLength(vector<int>& nums)
{
int n = nums.size();
vector<int> up(n, 1), down(n, 1);
int result = 1;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
up[i] = max(up[i], down[j] + 1);
} else if (nums[i] < nums[j]) {
down[i] = max(down[i], up[j] + 1);
}
}
result = max(result, max(up[i], down[i]));
}
return result;
}
};
Number of Longest Increasing Subsequences
Given an integer array nums, return the number of longest increasing subsequences.
DP Solution: We'll track both the length and count of LIS ending at each position. We'll maintain global variables for the maximum length and total count.
class Solution {
public:
int findNumberOfLIS(vector<int>& nums)
{
int n = nums.size();
vector<int> count(n, 1), length(n, 1);
int maxLen = 1, totalCount = 1;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
if (length[i] < length[j] + 1) {
length[i] = length[j] + 1;
count[i] = count[j];
} else if (length[i] == length[j] + 1) {
count[i] += count[j];
}
}
}
if (maxLen == length[i]) {
totalCount += count[i];
} else if (maxLen < length[i]) {
maxLen = length[i];
totalCount = count[i];
}
}
return totalCount;
}
};
Longest Pair Chain
You are given an array of pairs where each pair is represented as [a, b]. A pair (c, d) can follow another pair (a, b) if b < c. Return the length of the longest chain possible.
DP Solution: First sort the pairs by their first element, then find the longest chain using DP.
class Solution {
public:
int findLongestChain(vector<vector<int>>& pairs)
{
sort(pairs.begin(), pairs.end());
int n = pairs.size();
vector<int> chainLen(n, 1);
int maxChain = 1;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (pairs[i][0] > pairs[j][1]) {
chainLen[i] = max(chainLen[i], chainLen[j] + 1);
}
}
maxChain = max(maxChain, chainLen[i]);
}
return maxChain;
}
};
Longest Arithmetic Subsequence of Given Difefrence
Given an integer array arr and an integer difference, return the length of the longest arithmetic subsequence in arr such that the difference between adjacent elements is equal to difference.
Optimized DP Solution: Use a hash map to store the length of the longest valid subsequence ending at each value, achieving O(n) time complexity.
class Solution {
public:
int longestSubsequence(vector<int>& arr, int diff)
{
unordered_map<int, int> dp;
int maxLen = 0;
for (int num : arr) {
int prev = num - diff;
dp[num] = dp.count(prev) ? dp[prev] + 1 : 1;
maxLen = max(maxLen, dp[num]);
}
return maxLen;
}
};
Length of Longest Fibonacci Subsequence
Given a strictly increasing array of positive integers, find the length of the longest Fibonacci-like subsequence. A Fibonacci-like sequence is defined as having atleast 3 elements and each element being the sum of the two preceding elements.
DP Solution: Use a 2D DP array where dp[i][j] represents the length of the longest Fibonacci subsequence ending with elements at positions i and j.
class Solution {
public:
int lenLongestFibSubseq(vector<int>& arr)
{
int n = arr.size();
unordered_map<int, int> valueToIndex;
for (int i = 0; i < n; i++) {
valueToIndex[arr[i]] = i;
}
vector<vector<int>> dp(n, vector<int>(n, 2));
int maxLength = 0;
for (int j = 2; j < n; j++) {
for (int i = 1; i < j; i++) {
int needed = arr[j] - arr[i];
if (needed < arr[i] && valueToIndex.count(needed)) {
int k = valueToIndex[needed];
dp[i][j] = dp[k][i] + 1;
maxLength = max(maxLength, dp[i][j]);
}
}
}
return maxLength >= 3 ? maxLength : 0;
}
};