Category: algorithms

You have n  tiles, where each tile has one letter tiles[i] printed on it.

Return the number of possible non-empty sequences of letters you can make using the letters printed on those tiles.

Example 1:

Input: tiles = "AAB"
Output: 8
Explanation: The possible sequences are "A", "B", "AA", "AB", "BA", "AAB", "ABA", "BAA".

Example 2:

Input: tiles = "AAABBC"
Output: 188

Example 3:

Input: tiles = "V"
Output: 1

Depth First Search Solution, which is more performant with time complexity of O(N!) and space complexity of O(N).

class Solution {
public:
    int numTilePossibilities(string tiles) {
        unordered_map<char, int> count;
        for (char c : tiles) {
            count[c]++;
        }
        return dfs(count);
    }
    
private:
    int dfs(unordered_map<char, int>& count) {
        int sum = 0;
        for (auto& [tile, cnt] : count) {
            if (cnt == 0) continue;
            sum++;
            count[tile]--;
            sum += dfs(count);
            count[tile]++;
        }
        return sum;
    }
};

Backtracking Solution:

class Solution {
private: 
    set<string> seq;
    void backtrack(const string& tiles, string& current, vector<bool>& used){
        if( !current.empty() )
            seq.insert( current );
        for( int i =0; i<tiles.length();i++){
            if(used[i]) continue;
            used[i]=true;
            current.push_back(tiles[i]);
            backtrack(tiles, current, used);
            current.pop_back();
            used[i]=false;
        }
    }
public:
    
    int numTilePossibilities(string tiles) {
        vector<bool> used(tiles.length(), false);
        string current = "";        
        backtrack(tiles, current, used);
        return seq.size();
    }
};

Optimized Backtracking solution:

class Solution {
public:
void backtrack(unordered_map<char,int>&mapi,int &count){
    for(auto&entry:mapi){
    if(entry.second>0){
        entry.second--;
        count++;
        backtrack(mapi,count);
        entry.second++;
    }
    }
}
    int numTilePossibilities(string tiles) {
        unordered_map<char,int>mapi;
        for(int i=0;i<tiles.size();i++){
            mapi[tiles[i]]++;
        }
        int count=0;
         backtrack(mapi,count);
         return count;
    }
};

Given an array nums of distinct positive integers, return the number of tuples (a, b, c, d) such that a * b = c * d where a, b, c, and d are elements of nums, and a != b != c != d.

Example 1:

Input: nums = [2,3,4,6]
Output: 8
Explanation: There are 8 valid tuples:
(2,6,3,4) , (2,6,4,3) , (6,2,3,4) , (6,2,4,3)
(3,4,2,6) , (4,3,2,6) , (3,4,6,2) , (4,3,6,2)

Example 2:

Input: nums = [1,2,4,5,10]
Output: 16
Explanation: There are 16 valid tuples:
(1,10,2,5) , (1,10,5,2) , (10,1,2,5) , (10,1,5,2)
(2,5,1,10) , (2,5,10,1) , (5,2,1,10) , (5,2,10,1)
(2,10,4,5) , (2,10,5,4) , (10,2,4,5) , (10,2,5,4)
(4,5,2,10) , (4,5,10,2) , (5,4,2,10) , (5,4,10,2)

Constraints:

• 1 <= nums.length <= 1000
• 1 <= nums[i] <= 10<sup>4</sup>
• All elements in nums are distinct.

class Solution {
public:
    int tupleSameProduct(vector<int>& nums) {
        uint size = nums.size();
        unordered_map<int, int> mp;

        for( int i = 0; i < size; i++ )
            for( int j = i +1; j< size; j++){
                int prod  = nums[i] * nums[j];
                mp[prod]++;
            }
        
        int res = 0;
        for( auto& [prod, cnt] : mp ){
            int pairs = (cnt *(cnt-1)) / 2;
            res += 8 * pairs;
        }

        return res;
    }
};

class Solution {
public:
    int waysToSplitArray(vector<int>& nums) {
        // Keep track of sum of elements on left and right sides
        long long leftSum = 0, rightSum = 0;

        // Initially all elements are on right side
        for (int num : nums) {
            rightSum += num;
        }

        int count = 0;
        // Try each possible split position
        for (int i = 0; i < nums.size() - 1; i++) {
            // Move current element from right to left side
            leftSum += nums[i];
            rightSum -= nums[i];

            // Check if this creates a valid split
            if (leftSum >= rightSum) {
                count++;
            }
        }

        return count;
    }
};

You are given a 0-indexed integer array nums of length n.

nums contains a valid split at index i if the following are true:

• The sum of the first i + 1 elements is greater than or equal to the sum of the last n - i - 1 elements.
• There is at least one element to the right of i. That is, 0 <= i < n - 1.

Return the number of valid splits in nums.

Example 1:

Input: nums = [10,4,-8,7]
Output: 2
Explanation: 
There are three ways of splitting nums into two non-empty parts:
- Split nums at index 0. Then, the first part is [10], and its sum is 10. The second part is [4,-8,7], and its sum is 3. Since 10 >= 3, i = 0 is a valid split.
- Split nums at index 1. Then, the first part is [10,4], and its sum is 14. The second part is [-8,7], and its sum is -1. Since 14 >= -1, i = 1 is a valid split.
- Split nums at index 2. Then, the first part is [10,4,-8], and its sum is 6. The second part is [7], and its sum is 7. Since 6 < 7, i = 2 is not a valid split.
Thus, the number of valid splits in nums is 2.

Example 2:

Input: nums = [2,3,1,0]
Output: 2
Explanation: 
There are two valid splits in nums:
- Split nums at index 1. Then, the first part is [2,3], and its sum is 5. The second part is [1,0], and its sum is 1. Since 5 >= 1, i = 1 is a valid split. 
- Split nums at index 2. Then, the first part is [2,3,1], and its sum is 6. The second part is [0], and its sum is 0. Since 6 >= 0, i = 2 is a valid split.

Constraints:

• 2 <= nums.length <= 10<sup>5</sup>
• -10<sup>5</sup> <= nums[i] <= 10<sup>5</sup>

Given the integers zero, one, low, and high, we can construct a string by starting with an empty string, and then at each step perform either of the following:

• Append the character '0' zero times.
• Append the character '1' one times.

This can be performed any number of times.

A good string is a string constructed by the above process having a length between low and high (inclusive).

Return the number of different good strings that can be constructed satisfying these properties. Since the answer can be large, return it modulo 10<sup>9</sup> + 7.

Input: low = 3, high = 3, zero = 1, one = 1
Output: 8
Explanation: 
One possible valid good string is "011". 
It can be constructed as follows: "" -> "0" -> "01" -> "011". 
All binary strings from "000" to "111" are good strings in this example.

Input: low = 2, high = 3, zero = 1, one = 2
Output: 5
Explanation: The good strings are "00", "11", "000", "110", and "011".

Solution: fastest one is using tabulation dynamic programming technique.

    int countGoodStrings(int low, int high, int zero, int one) {
        int sum[100001];
        sum[0] = 1;
        for (int i = 1; i <= high; i++)
        {
            long long sumCur = 0;
            if (i >= zero)
                sumCur += sum[i-zero];
            if (i >= one)
                sumCur += sum[i-one];
            if (sumCur > 0x3000000000000000ll)
                sumCur %= 1000000007;
            sum[i] = sumCur % 1000000007;
        }

        long long sumTotal = 0;
        for (int i = low; i <= high; i++)
            sumTotal += sum[i];
        return sumTotal % 1000000007;
    }

Way slower approach is to use a map in your code for memoization, and a recursive DFS method.

class Solution {
public:
    int countGoodStrings(int low, int high, int zero, int one) {
        map<int, int> dp;
        long mod = pow(10,9) +7;    
        function<int(int)> dfs = [&](int length) -> int{
            
            if( length > high ) return 0;

            if(dp.find(length) != dp.end() )
                return dp[length];

            int count = ( length >= low) ? 1 : 0;
            count = (count + dfs(length + zero)) % mod;
            count = (count + dfs(length + one)) % mod;
            
            return dp[length] = count;
        };

        return dfs(0);    
    }
};

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this

Input: s = "PAYPALISHIRING", numRows = 3 Output: "PAHNAPLSIIGYIR"
P   A   H   N
A P L S I I G
Y   I   R

Input: s = "PAYPALISHIRING", numRows = 4 Output: "PINALSIGYAHRPI"
P     I    N
A   L S  I G
Y A   H R
P     I

Solution

#include <iostream>
#include <string>
using namespace std;

class Solution {
public:
    string convert(string s, int numRows) {
        int n = s.size();
        if (n == 1 || numRows < 2 || n <= numRows) return s;
        
        string ans;
        
        for (int i = 0; i < numRows; i++) {
            int j = i;
            ans.push_back(s[i]); // First character of the row
            int down = 2 * (numRows - 1 - i); // Downward step size
            int up = 2 * i; // Upward step size
            
            if (up == 0 && down == 0) return s; // If no movement, just return the string
            
            while (j < n) {
                j += down;
                if (j < n && down > 0) ans.push_back(s[j]);
                
                j += up;
                if (j < n && up > 0) ans.push_back(s[j]);
            }
        }
        
        return ans;
    }
};

int main() {
    Solution solution;
    string s = "PAYPALISHIRING"; // Example input
    int numRows = 3; // Example row count
    
    string result = solution.convert(s, numRows);
    cout << "Zigzag Conversion: " << result << endl; // Output the result
    return 0;
}