Q1.

Maximum Score from Subarray Minimums

C++ Solution
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
int pairWithMaxSum(vector<int>& arr) {
int n = [Link]();
int maxSum = 0;

for (int i = 1; i < n; i++) {

maxSum = max(maxSum, arr[i] + arr[i-1]);
}

return maxSum;
}
};

Java Solution

java
import [Link].*;

class Solution {
public int pairWithMaxSum(List<Integer> arr) {
int n = [Link]();
int maxSum = 0;

for (int i = 1; i < n; i++) {

maxSum = [Link](maxSum, [Link](i) + [Link](i-1));
}

Material Copyrighted @KNACADEMYCOURSES

 return maxSum;
}
}

Python Solution

python
class Solution:
def pairWithMaxSum(self, arr):
n = len(arr)
max_sum = 0

for i in range(1, n):

max_sum = max(max_sum, arr[i] + arr[i-1])

return max_sum

Q2. Max-so-far Count Problem

C++ Solution

cpp
#include <iostream>
#include <climits>
using namespace std;

int main() {
int n;
cin >> n;

if (n < 1 || n > 20) {

cout << "Invalid input size" << endl;
return 1;
}

int count = 0;
int maxSoFar = INT_MIN;

Material Copyrighted @KNACADEMYCOURSES

 for (int i = 0; i < n; i++) {
int num;
cin >> num;

if (num > maxSoFar) {

maxSoFar = num;
count++;
}
}

cout << count << endl;

return 0;
}

Java Solution

java
import [Link];

public class Main {

public static void main(String[] args) {
Scanner sc = new Scanner([Link]);

int n = [Link]();

if (n < 1 || n > 20) {

[Link]("Invalid input size");
return;
}

int count = 0;
int maxSoFar = Integer.MIN_VALUE;

Material Copyrighted @KNACADEMYCOURSES

 for (int i = 0; i < n; i++) {
int num = [Link]();

if (num > maxSoFar) {

maxSoFar = num;
count++;
}
}

[Link](count);
[Link]();
}
}

Python Solution

python
def main():
n = int(input())

if n < 1 or n > 20:

print("Invalid input size")
return

count = 0
max_so_far = float('-inf')

for _ in range(n):
num = int(input())
if num > max_so_far:
max_so_far = num
count += 1

print(count)

Material Copyrighted @KNACADEMYCOURSES

if __name__ == "__main__":
main()

Q3. 3 Sum

C++ Solution

cpp
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> result;
int n = [Link]();

if (n < 3) return result;

sort([Link](), [Link]());

for (int i = 0; i < n - 2; i++) {

if (i > 0 && nums[i] == nums[i-1]) continue;

int left = i + 1;
int right = n - 1;

while (left < right) {

int sum = nums[i] + nums[left] + nums[right];

if (sum == 0) {
result.push_back({nums[i], nums[left],
nums[right]});

Material Copyrighted @KNACADEMYCOURSES

 while (left < right && nums[left] ==
nums[left+1]) left++;
while (left < right && nums[right] ==
nums[right-1]) right--;

left++;
right--;
}
else if (sum < 0) {
left++;
}
else {
right--;
}
}
}

return result;
}
};

Java Solution

java
import [Link].*;

class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
int n = [Link];

if (n < 3) return result;

[Link](nums);

Material Copyrighted @KNACADEMYCOURSES

 for (int i = 0; i < n - 2; i++) {
if (i > 0 && nums[i] == nums[i-1]) continue;

int left = i + 1;
int right = n - 1;

while (left < right) {

int sum = nums[i] + nums[left] + nums[right];

if (sum == 0) {
[Link]([Link](nums[i], nums[left],
nums[right]));

while (left < right && nums[left] ==

nums[left+1]) left++;
while (left < right && nums[right] ==
nums[right-1]) right--;

left++;
right--;
}
else if (sum < 0) {
left++;
}
else {
right--;
}
}
}

return result;
}
}

Python Solution

Material Copyrighted @KNACADEMYCOURSES

python
class Solution:
def threeSum(self, nums):
result = []
n = len(nums)

if n < 3:
return result

[Link]()

for i in range(n - 2):

if i > 0 and nums[i] == nums[i-1]:
continue

left, right = i + 1, n - 1

while left < right:

total = nums[i] + nums[left] + nums[right]

if total == 0:
[Link]([nums[i], nums[left],
nums[right]])

while left < right and nums[left] ==

nums[left+1]:
left += 1
while left < right and nums[right] ==
nums[right-1]:
right -= 1

left += 1
right -= 1
elif total < 0:

Material Copyrighted @KNACADEMYCOURSES

 left += 1
else:
right -= 1

return result

Q4. Partition Equal Subset Sum

C++ Solution

cpp
#include <vector>
using namespace std;

class Solution {
public:
int equalPartition(int N, int arr[]) {
int sum = 0;
for (int i = 0; i < N; i++) {
sum += arr[i];
}

if (sum % 2 != 0) return 0;

int target = sum / 2;

vector<vector<bool>> dp(N + 1, vector<bool>(target + 1,
false));

for (int i = 0; i <= N; i++) {

dp[i][0] = true;
}

for (int i = 1; i <= N; i++) {

for (int j = 1; j <= target; j++) {
if (arr[i-1] <= j) {
dp[i][j] = dp[i-1][j] || dp[i-1][j - arr[i-1]];

Material Copyrighted @KNACADEMYCOURSES

 } else {
dp[i][j] = dp[i-1][j];
}
}
}

return dp[N][target] ? 1 : 0;
}
};

Java Solution

java
class Solution {
static int equalPartition(int N, int arr[]) {
int sum = 0;
for (int i = 0; i < N; i++) {
sum += arr[i];
}

if (sum % 2 != 0) return 0;

int target = sum / 2;

boolean[][] dp = new boolean[N + 1][target + 1];

for (int i = 0; i <= N; i++) {

dp[i][0] = true;
}

for (int i = 1; i <= N; i++) {

for (int j = 1; j <= target; j++) {
if (arr[i-1] <= j) {
dp[i][j] = dp[i-1][j] || dp[i-1][j - arr[i-1]];
} else {

Material Copyrighted @KNACADEMYCOURSES

 dp[i][j] = dp[i-1][j];
}
}
}

return dp[N][target] ? 1 : 0;
}
}

Python Solution

python
class Solution:
def equalPartition(self, N, arr):
total = sum(arr)

if total % 2 != 0:
return 0

target = total // 2
dp = [[False] * (target + 1) for _ in range(N + 1)]

for i in range(N + 1):

dp[i][0] = True

for i in range(1, N + 1):

for j in range(1, target + 1):
if arr[i-1] <= j:
dp[i][j] = dp[i-1][j] or dp[i-1][j - arr[i-1]]
else:
dp[i][j] = dp[i-1][j]

return 1 if dp[N][target] else 0

Q5. Rotate Matrix By 90 Degree

Material Copyrighted @KNACADEMYCOURSES

C++ Solution

cpp
#include <vector>
using namespace std;

class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int n = [Link]();

// Transpose
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
swap(matrix[i][j], matrix[j][i]);
}
}

// Reverse each row

for (int i = 0; i < n; i++) {
reverse(matrix[i].begin(), matrix[i].end());
}
}
};

Java Solution

java
class Solution {
public void rotate(int[][] matrix) {
int n = [Link];

// Transpose
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {

Material Copyrighted @KNACADEMYCOURSES

 int temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}

// Reverse each row

for (int i = 0; i < n; i++) {
for (int j = 0; j < n / 2; j++) {
int temp = matrix[i][j];
matrix[i][j] = matrix[i][n - 1 - j];
matrix[i][n - 1 - j] = temp;
}
}
}
}

Python Solution

python
class Solution:
def rotate(self, matrix):
n = len(matrix)

# Transpose
for i in range(n):
for j in range(i + 1, n):
matrix[i][j], matrix[j][i] = matrix[j][i],
matrix[i][j]

# Reverse each row

for i in range(n):
matrix[i].reverse()

Q6. Best Time to Buy and Sell Stock

C++ Solution

Material Copyrighted @KNACADEMYCOURSES

cpp
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

int maximumProfit(vector<int> &prices) {

int n = [Link]();
if (n <= 1) return 0;

int minPrice = prices[0];

int maxProfit = 0;

for (int i = 1; i < n; i++) {

minPrice = min(minPrice, prices[i]);
maxProfit = max(maxProfit, prices[i] - minPrice);
}

return maxProfit;
}

Java Solution

java
import [Link];

public class Solution {

public static int maximumProfit(ArrayList<Integer> prices) {
int n = [Link]();
if (n <= 1) return 0;

int minPrice = [Link](0);

int maxProfit = 0;

Material Copyrighted @KNACADEMYCOURSES

 for (int i = 1; i < n; i++) {
minPrice = [Link](minPrice, [Link](i));
maxProfit = [Link](maxProfit, [Link](i) -
minPrice);
}

return maxProfit;
}
}

Python Solution

python
def maximumProfit(prices):
n = len(prices)
if n <= 1:
return 0

min_price = prices[0]
max_profit = 0

for i in range(1, n):

min_price = min(min_price, prices[i])
max_profit = max(max_profit, prices[i] - min_price)

return max_profit

Q7. Minimum Swaps

C++ Solution

cpp
#include <vector>
#include <algorithm>
using namespace std;

int minimumSwaps(vector<int> &arr, int n, int k) {

int count = 0;

Material Copyrighted @KNACADEMYCOURSES

 for (int i = 0; i < n; i++) {
if (arr[i] <= k) count++;
}

if (count == 0) return 0;

int bad = 0;
for (int i = 0; i < count; i++) {
if (arr[i] > k) bad++;
}

int minSwaps = bad;

for (int i = count; i < n; i++) {

if (arr[i - count] > k) bad--;
if (arr[i] > k) bad++;
minSwaps = min(minSwaps, bad);
}

return minSwaps;
}

Java Solution

java
import [Link];

public class Solution {

public static int minimumSwaps(ArrayList<Integer> arr, int n,
int k) {
int count = 0;
for (int i = 0; i < n; i++) {
if ([Link](i) <= k) count++;
}

Material Copyrighted @KNACADEMYCOURSES

 if (count == 0) return 0;

int bad = 0;
for (int i = 0; i < count; i++) {
if ([Link](i) > k) bad++;
}

int minSwaps = bad;

for (int i = count; i < n; i++) {

if ([Link](i - count) > k) bad--;
if ([Link](i) > k) bad++;
minSwaps = [Link](minSwaps, bad);
}

return minSwaps;
}
}

Python Solution

python
def minimumSwaps(arr, n, k):
count = sum(1 for x in arr if x <= k)

if count == 0:
return 0

bad = sum(1 for i in range(count) if arr[i] > k)

min_swaps = bad

for i in range(count, n):

if arr[i - count] > k:
bad -= 1

Material Copyrighted @KNACADEMYCOURSES

 if arr[i] > k:
bad += 1
min_swaps = min(min_swaps, bad)

return min_swaps

Q8. Chocolate Problem

C++ Solution

cpp
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

int findMinDiff(int n, int m, vector<int> chocolates) {

if (m == 0 || n == 0) return 0;
if (n < m) return -1;

sort([Link](), [Link]());

int minDiff = INT_MAX;

for (int i = 0; i + m - 1 < n; i++) {

int diff = chocolates[i + m - 1] - chocolates[i];
minDiff = min(minDiff, diff);
}

return minDiff;
}

Java Solution

java
import [Link].*;

Material Copyrighted @KNACADEMYCOURSES

public class Solution {
static int findMinDiff(int n, int m, ArrayList<Integer>
chocolates) {
if (m == 0 || n == 0) return 0;
if (n < m) return -1;

[Link](chocolates);

int minDiff = Integer.MAX_VALUE;

for (int i = 0; i + m - 1 < n; i++) {

int diff = [Link](i + m - 1) -
[Link](i);
minDiff = [Link](minDiff, diff);
}

return minDiff;
}
}

Python Solution

python
def findMinDiff(n, m, chocolates):
if m == 0 or n == 0:
return 0
if n < m:
return -1

[Link]()

min_diff = float('inf')

for i in range(n - m + 1):

diff = chocolates[i + m - 1] - chocolates[i]

Material Copyrighted @KNACADEMYCOURSES

 min_diff = min(min_diff, diff)

return min_diff

Q9. Trapping Rain Water

C++ Solution

cpp
#include <vector>
#include <algorithm>
using namespace std;

long long getTrappedWater(long long* arr, int n) {

if (n <= 2) return 0;

vector<long long> leftMax(n), rightMax(n);

leftMax[0] = arr[0];
for (int i = 1; i < n; i++) {
leftMax[i] = max(leftMax[i-1], arr[i]);
}

rightMax[n-1] = arr[n-1];
for (int i = n-2; i >= 0; i--) {
rightMax[i] = max(rightMax[i+1], arr[i]);
}

long long water = 0;

for (int i = 0; i < n; i++) {
water += min(leftMax[i], rightMax[i]) - arr[i];
}

return water;
}

Material Copyrighted @KNACADEMYCOURSES

Java Solution

java
public class Solution {
public static long getTrappedWater(long[] arr, int n) {
if (n <= 2) return 0;

long[] leftMax = new long[n];

long[] rightMax = new long[n];

leftMax[0] = arr[0];
for (int i = 1; i < n; i++) {
leftMax[i] = [Link](leftMax[i-1], arr[i]);
}

rightMax[n-1] = arr[n-1];
for (int i = n-2; i >= 0; i--) {
rightMax[i] = [Link](rightMax[i+1], arr[i]);
}

long water = 0;
for (int i = 0; i < n; i++) {
water += [Link](leftMax[i], rightMax[i]) - arr[i];
}

return water;
}
}

Python Solution

python
def getTrappedWater(arr, n):
if n <= 2:
return 0

Material Copyrighted @KNACADEMYCOURSES

 left_max = [0] * n
right_max = [0] * n

left_max[0] = arr[0]
for i in range(1, n):
left_max[i] = max(left_max[i-1], arr[i])

right_max[n-1] = arr[n-1]
for i in range(n-2, -1, -1):
right_max[i] = max(right_max[i+1], arr[i])

water = 0
for i in range(n):
water += min(left_max[i], right_max[i]) - arr[i]

return water

Q10. Kth Smallest

C++ Solution

cpp
#include <vector>
#include <queue>
using namespace std;

class Solution {
public:
int kthSmallest(int arr[], int l, int r, int k) {
priority_queue<int> maxHeap;

for (int i = l; i <= r; i++) {

[Link](arr[i]);
if ([Link]() > k) {

Material Copyrighted @KNACADEMYCOURSES

 [Link]();
}
}

return [Link]();
}
};

Java Solution

java
import [Link].*;

class Solution {
public static int kthSmallest(int[] arr, int l, int r, int k) {
PriorityQueue<Integer> maxHeap = new
PriorityQueue<>([Link]());

for (int i = l; i <= r; i++) {

[Link](arr[i]);
if ([Link]() > k) {
[Link]();
}
}

return [Link]();
}
}

Python Solution

python
import heapq

class Solution:
def kthSmallest(self, arr, l, r, k):
max_heap = []

Material Copyrighted @KNACADEMYCOURSES

 for i in range(l, r + 1):
[Link](max_heap, -arr[i])
if len(max_heap) > k:
[Link](max_heap)

return -max_heap[0]

Q11. Minimum Platforms

C++ Solution

cpp
#include <vector>
#include <algorithm>
using namespace std;

int findPlatform(int arr[], int dep[], int n) {

sort(arr, arr + n);
sort(dep, dep + n);

int platforms = 1, result = 1;

int i = 1, j = 0;

while (i < n && j < n) {

if (arr[i] <= dep[j]) {
platforms++;
i++;
} else {
platforms--;
j++;
}
result = max(result, platforms);
}

Material Copyrighted @KNACADEMYCOURSES

 return result;
}

Java Solution

java
import [Link].*;

class GFG {
public static int findPlatform(int arr[], int dep[], int n) {
[Link](arr);
[Link](dep);

int platforms = 1, result = 1;

int i = 1, j = 0;

while (i < n && j < n) {

if (arr[i] <= dep[j]) {
platforms++;
i++;
} else {
platforms--;
j++;
}
result = [Link](result, platforms);
}

return result;
}
}
Python Solution
python
def findPlatform(arr, dep, n):
[Link]()

Material Copyrighted @KNACADEMYCOURSES

 [Link]()

platforms = 1
result = 1
i, j = 1, 0

while i < n and j < n:

if arr[i] <= dep[j]:
platforms += 1
i += 1
else:
platforms -= 1
j += 1
result = max(result, platforms)

return result

Q12. Stock Span Problem

C++ Solution

cpp
#include <vector>
#include <stack>
using namespace std;

vector<int> calculateSpan(int price[], int n) {

vector<int> span(n);
stack<int> st;

[Link](0);
span[0] = 1;

for (int i = 1; i < n; i++) {

while (![Link]() && price[[Link]()] <= price[i]) {

Material Copyrighted @KNACADEMYCOURSES

 [Link]();
}

span[i] = [Link]() ? i + 1 : i - [Link]();

[Link](i);
}

return span;
}

Java Solution

java
import [Link].*;

class GFG {
static int[] calculateSpan(int price[], int n) {
int[] span = new int[n];
Stack<Integer> st = new Stack<>();

[Link](0);
span[0] = 1;

for (int i = 1; i < n; i++) {

while (![Link]() && price[[Link]()] <= price[i]) {
[Link]();
}

span[i] = [Link]() ? i + 1 : i - [Link]();

[Link](i);
}

return span;
}

Material Copyrighted @KNACADEMYCOURSES

}

Python Solution

python
def calculateSpan(price, n):
span = [0] * n
stack = []

[Link](0)
span[0] = 1

for i in range(1, n):

while stack and price[stack[-1]] <= price[i]:
[Link]()

span[i] = i + 1 if not stack else i - stack[-1]

[Link](i)

return span

Q13. Travelling Salesman Problem

C++ Solution

cpp
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

class Solution {
public:
int total_cost(vector<vector<int>> cost) {
int n = [Link]();
vector<vector<int>> dp(1 << n, vector<int>(n, -1));

Material Copyrighted @KNACADEMYCOURSES

 return tsp(1, 0, cost, dp);
}

private:
int tsp(int mask, int pos, vector<vector<int>>& cost,
vector<vector<int>>& dp) {
int n = [Link]();

if (mask == (1 << n) - 1) {
return cost[pos][0];
}

if (dp[mask][pos] != -1) {
return dp[mask][pos];
}

int ans = INT_MAX;

for (int city = 0; city < n; city++) {

if ((mask & (1 << city)) == 0) {
int newCost = cost[pos][city] + tsp(mask | (1 <<
city), city, cost, dp);
ans = min(ans, newCost);
}
}

return dp[mask][pos] = ans;

}
};

Java Solution

java
import [Link].*;

Material Copyrighted @KNACADEMYCOURSES

class Solution {
public int total_cost(int[][] cost) {
int n = [Link];
int[][] dp = new int[1 << n][n];

for (int[] row : dp) {

[Link](row, -1);
}

return tsp(1, 0, cost, dp);

}

private int tsp(int mask, int pos, int[][] cost, int[][] dp) {
int n = [Link];

if (mask == (1 << n) - 1) {
return cost[pos][0];
}

if (dp[mask][pos] != -1) {
return dp[mask][pos];
}

int ans = Integer.MAX_VALUE;

for (int city = 0; city < n; city++) {

if ((mask & (1 << city)) == 0) {
int newCost = cost[pos][city] + tsp(mask | (1 <<
city), city, cost, dp);
ans = [Link](ans, newCost);
}
}

Material Copyrighted @KNACADEMYCOURSES

 return dp[mask][pos] = ans;
}
}

Python Solution

python
class Solution:
def total_cost(self, cost):
n = len(cost)
dp = [[-1] * n for _ in range(1 << n)]

return [Link](1, 0, cost, dp)

def tsp(self, mask, pos, cost, dp):

n = len(cost)

if mask == (1 << n) - 1:
return cost[pos][0]

if dp[mask][pos] != -1:
return dp[mask][pos]

ans = float('inf')

for city in range(n):

if (mask & (1 << city)) == 0:
new_cost = cost[pos][city] + [Link](mask | (1 <<
city), city, cost, dp)
ans = min(ans, new_cost)

dp[mask][pos] = ans
return ans

Q14. Cake Distribution Problem

C++ Solution

Material Copyrighted @KNACADEMYCOURSES

cpp
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

class Solution {
public:
int maxSweetness(vector<int>& sweetness, int n, int k) {
int low = *min_element([Link](), [Link]());
int high = 0;
for (int s : sweetness) high += s;

int result = low;

while (low <= high) {

int mid = low + (high - low) / 2;

if (canSplit(sweetness, n, k + 1, mid)) {
result = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}

return result;
}

private:
bool canSplit(vector<int>& sweetness, int n, int pieces, int
minSweetness) {
int current = 0;

Material Copyrighted @KNACADEMYCOURSES

 int count = 0;

for (int i = 0; i < n; i++) {

current += sweetness[i];
if (current >= minSweetness) {
count++;
current = 0;
}
}

return count >= pieces;

}
};

Java Solution

java
import [Link].*;

class Solution {
int maxSweetness(int[] sweetness, int n, int k) {
int low = Integer.MAX_VALUE;
int high = 0;

for (int s : sweetness) {

low = [Link](low, s);
high += s;
}

int result = low;

while (low <= high) {

int mid = low + (high - low) / 2;

Material Copyrighted @KNACADEMYCOURSES

 if (canSplit(sweetness, n, k + 1, mid)) {
result = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}

return result;
}

private boolean canSplit(int[] sweetness, int n, int pieces, int

minSweetness) {
int current = 0;
int count = 0;

for (int i = 0; i < n; i++) {

current += sweetness[i];
if (current >= minSweetness) {
count++;
current = 0;
}
}

return count >= pieces;

}
}

Python Solution

python
class Solution:
def maxSweetness(self, sweetness, n, k):
low = min(sweetness)
high = sum(sweetness)

Material Copyrighted @KNACADEMYCOURSES

 result = low

while low <= high:

mid = (low + high) // 2

if self.can_split(sweetness, n, k + 1, mid):
result = mid
low = mid + 1
else:
high = mid - 1

return result

def can_split(self, sweetness, n, pieces, min_sweetness):

current = 0
count = 0

for i in range(n):
current += sweetness[i]
if current >= min_sweetness:
count += 1
current = 0

return count >= pieces

Q15. Little Bear and Strings

C++ Solution

cpp
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <set>

Material Copyrighted @KNACADEMYCOURSES

using namespace std;

class Solution {
public:
int countDistinctGoodSubstrings(string s, string t1, string t2)
{
int n = [Link]();
int l1 = [Link](), l2 = [Link]();

vector<int> startPositions, endPositions;

// Find all positions where t1 starts

for (int i = 0; i <= n - l1; i++) {
if ([Link](i, l1) == t1) {
startPositions.push_back(i);
}
}

// Find all positions where t2 ends

for (int i = l2 - 1; i < n; i++) {
if ([Link](i - l2 + 1, l2) == t2) {
endPositions.push_back(i);
}
}

if ([Link]() || [Link]()) {
return 0;
}

set<string> distinctSubstrings;

for (int start : startPositions) {

for (int end : endPositions) {

Material Copyrighted @KNACADEMYCOURSES

 if (end >= start) {
[Link]([Link](start, end -
start + 1));
}
}
}

return [Link]();
}
};

int main() {
Solution sol;
string s, t1, t2;

while (getline(cin, s) && getline(cin, t1) && getline(cin, t2))

{
cout << [Link](s, t1, t2) << endl;
}

return 0;
}

Java Solution

java
import [Link].*;

class Solution {
public int countDistinctGoodSubstrings(String s, String t1,
String t2) {
int n = [Link]();
int l1 = [Link](), l2 = [Link]();

List<Integer> startPositions = new ArrayList<>();

Material Copyrighted @KNACADEMYCOURSES

 List<Integer> endPositions = new ArrayList<>();

// Find all positions where t1 starts

for (int i = 0; i <= n - l1; i++) {
if ([Link](i, i + l1).equals(t1)) {
[Link](i);
}
}

// Find all positions where t2 ends

for (int i = l2 - 1; i < n; i++) {
if ([Link](i - l2 + 1, i + 1).equals(t2)) {
[Link](i);
}
}

if ([Link]() || [Link]()) {
return 0;
}

Set<String> distinctSubstrings = new HashSet<>();

for (int start : startPositions) {

for (int end : endPositions) {
if (end >= start) {
[Link]([Link](start, end +
1));
}
}
}

return [Link]();
}

Material Copyrighted @KNACADEMYCOURSES

 public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
Solution sol = new Solution();

while ([Link]()) {
String s = [Link]();
if (![Link]()) break;
String t1 = [Link]();
if (![Link]()) break;
String t2 = [Link]();

[Link]([Link](s,
t1, t2));
}

[Link]();
}
}

Python Solution

python
class Solution:
def countDistinctGoodSubstrings(self, s, t1, t2):
n = len(s)
l1, l2 = len(t1), len(t2)

start_positions = []
end_positions = []

# Find all positions where t1 starts

for i in range(n - l1 + 1):
if s[i:i + l1] == t1:
start_positions.append(i)

Material Copyrighted @KNACADEMYCOURSES

 # Find all positions where t2 ends
for i in range(l2 - 1, n):
if s[i - l2 + 1:i + 1] == t2:
end_positions.append(i)

if not start_positions or not end_positions:

return 0

distinct_substrings = set()

for start in start_positions:

for end in end_positions:
if end >= start:
distinct_substrings.add(s[start:end + 1])

return len(distinct_substrings)

def main():
import sys
sol = Solution()
lines = [[Link]() for line in [Link] if [Link]()]

for i in range(0, len(lines), 3):

if i + 2 < len(lines):
s = lines[i]
t1 = lines[i + 1]
t2 = lines[i + 2]
print([Link](s, t1, t2))

if __name__ == "__main__":
main()

Material Copyrighted @KNACADEMYCOURSES

Material Copyrighted @KNACADEMYCOURSES