Problem1 (Triplets Within Range) Solution -:

Topics -: Sorting,Sliding Window / Two Pointers, Combinatorics (nCr)

 Sorting the array first allows us to easily lock in the smallest element of our potential triplet and search for valid maximum boundaries. By using a sliding window, we can efficiently find exactly how many subsequent numbers fall within the allowed difference d from our starting number. Once that boundary is found, choosing the remaining two triplet members from the available numbers is just a simple combinatorial math calculation.

Approach

1. Sorting and the Sliding Window Because we are picking a group of three numbers where the order doesn't matter, we should sort the array first. We iterate through the array, treating each number arr[i] as the absolute smallest number in our triplet. We then push a second pointer, j, forward until the difference between arr[j] and arr[i] exceeds d.

2. Calculating the Combinations When the j pointer stops, every number strictly between index i and index j - 1 is a valid candidate for the triplet. If we have count numbers available in this window, we just need to pick exactly 2 of them to complete the triplet with arr[i]. The mathematical formula to choose 2 items from a pool is count * (count - 1) / 2. We add this to our total sum, applying the modulo at each step to prevent overflow.

function countTriplets(n, arr, d):
    MOD = 1000000007
    sort(arr)
    ans = 0
    j = 0
    

    for i from 0 to n - 1:
       
        while j < n AND arr[j] - arr[i] <= d:
            j = j + 1
            
    
        count = (j - 1) - i
        
        // If we have at least 2 numbers to pick from, calculate combinations
        if count >= 2:
            ways = (count * (count - 1)) / 2
            ans = (ans + ways) % MOD
            
    return ans

Time Complexity

• Time: O(T log T) - Database engines generally perform sorting and joining operations efficiently, scaling relative to the number of records and internal indexing.

Space: O(U) - Where U is the number of unique wallets participating in transactions that must be held in memory for sorting and returning.

Problem2 

Sub-Palindrome Solution

Topics Involved / Prerequisites

• Expand Around Center
• Hash Sets
• String Manipulation

Overview

A palindrome perfectly mirrors itself from its center, meaning we can find them all by treating every character and the space between characters as a midpoint.

As we expand outwards from each midpoint, we extract the valid palindromic strings and store them in a hash set.

Because hash sets automatically filter out duplicates, the final size of the set gives us the exact count of uniquely distinct palindromes.

Approach

1. Expanding Around the Center

There are 2N - 1 possible centers in a string (every single character can be a center for odd-length palindromes, and the space between every pair of adjacent characters can be a center for even-length palindromes). We iterate through the string and use two pointers (left and right) to expand outwards from these centers as long as the characters match.

2. Extracting and Storing

Every time we successfully expand and find matching characters, the string between left and right is a valid palindrome! We extract that substring and insert it directly into a Hash Set. If we find the exact same palindrome later in the string, the Hash Set will simply ignore it. Once we check all centers, the number of elements in the Hash Set is our final answer.

Time Complexity

• Time: O(N^2) - In the worst-case scenario (a string of all identical characters), we expand O(N) times for each of the O(N) centers. Substring extraction adds a minor overhead.
• Space: O(N^2) - In the worst case, we might store many distinct substrings in the Hash Set.

Code Implementation (Pseudocode)

function countDistinctPalindromes(s):
    create an empty Hash Set 'uniquePalindromes'
    n = length of s
    function expand(l, r):
        while l >= 0 AND r < n AND s[l] == s[r]:
            // Extract the substring and add it to our Set
            sub = s.substring(l, r - l + 1)
            uniquePalindromes.insert(sub)
            
            // Expand outwards
            l = l - 1
            r = r + 1
    for i from 0 to n - 1:
   
        expand(i, i)
        expand(i, i + 1)
    return uniquePalindromes.size()