Second Largest Digit in a String

Given an alphanumeric string s, return the second largest numerical digit that appears in s, or -1 if it does not exist.

An alphanumeric string is a string consisting of lowercase English letters and digits.

Example 1:

Input: s = "dfa12321afd"
Output: 2
Explanation: The digits that appear in s are [1, 2, 3]. The second largest digit is 2.

Example 2:

Input: s = "abc1111"
Output: -1
Explanation: The digits that appear in s are [1]. There is no second largest digit. 

Approach

C++

#include <bits/stdc++.h>
using namespace std;

int secondHighest(string s)
{
    int n = s.size();
    int i = 0;
    set<int> st;
    while (i < n)
    {
        while (i < n && !(s[i] >= '0' && s[i] <= '9'))
            i++;
        while (i < n && s[i] >= '0' && s[i] <= '9')
        {
            st.insert(s[i] - '0');
            i++;
        }
    }
    if (st.size() >= 2)
    {
        vector<int> vec;
        for (auto it = st.begin(); it != st.end(); it++)
            vec.push_back(*it);
        sort(vec.begin(), vec.end());
        return vec[vec.size() - 2];
    }
    return -1;
}

int main()
{
    string s = "dfa12321afd";

    cout << secondHighest(s) << "\n";

    return 0;
}

Number of Different Integers in a String

You are given a string word that consists of digits and lowercase English letters.

You will replace every non-digit character with space. For example, "a123bc34d8ef34" will become " 123  34 8  34". Notice that you are left with some integers that are separated by at least one space: "123", "34", "8", and "34".

Return the number of different integers after performing the replacement operations on word.

Two integers are considered different if their decimal representations without any leading zeros are different.

Example 1:

Input: word = "a123bc34d8ef34"
Output: 3
Explanation: The three different integers are "123", "34", and "8". Notice that "34" is only counted once.

Example 2:

Input: word = "leet1234code234"
Output: 2

Approach

C++

#include <bits/stdc++.h>
using namespace std;

int numDifferentIntegers(string s)
{

    int n = s.size();
    int i = 0;
    set<string> st;
    while (i < n)
    {
        while (i < n && !(s[i] >= '0' && s[i] <= '9'))
            i++;
        string str = "";
        while (i < n && s[i] >= '0' && s[i] <= '9')
        {
            str += s[i];
            i++;
        }
        if (str.size() > 0)
        {
            int j = 0;
            while (j < str.size() && str[j] == '0')
                j++;
            str = str.substr(j);
            st.insert(str);
        }
    }

    return st.size();
}

int main()
{
    string word = "a123bc34d8ef34";

    cout << numDifferentIntegers(word) << "\n";

    return 0;
}

Find element which appears half of length of array

Given a list of elements, find the majority element, which appears more than half the time (> floor(len(lst) / 2.0)).

You can assume that such an element exists.

For example, given [1, 2, 1, 1, 3, 4, 0], return 1.

Example:

Input: arr = {1, 2, 1, 1, 3, 4, 0}
Output: 1

Approach

C++

#include <bits/stdc++.h>
using namespace std;

int findMajorityElement(vector<int> &arr)
{
    sort(arr.begin(), arr.end());

    int n = arr.size();

    return arr[n / 2];
}
int main()
{

    vector<int> arr = {1, 2, 1, 1, 3, 4, 0};

    cout << findMajorityElement(arr) << "\n";

    return 0;
}

Find the smallest number of squared integers which sum to N

Given a positive integer n, find the smallest number of squared integers which sum to n.

For example, given n = 13, return 2 since 13 = 3² + 2² = 9 + 4.

Given n = 27, return 3 since 27 = 3² + 3² + 3² = 9 + 9 + 9.

Example:

Input:  n = 13
Output: 2  // 2*2+3*3

Approach

C++

#include <bits/stdc++.h>
using namespace std;

int minPerfectSquareSumN(int num)
{
    int dp[num + 1];

    if (num == 1)
        return 1;
    for (int i = 0; i <= num; i++)
    {
        dp[i] = i;
        for (int j = 1; j * j <= i; j++)
        {
            dp[i] = min(dp[i], 1 + dp[i - j * j]);
        }
    }
    return dp[num];
}
int main()
{
    int num = 13;

    cout << minPerfectSquareSumN(num) << "\n";

    return 0;
}

Number of ways to move from top left corner to bottom right corner

You are given an N by M matrix of 0s and 1s. Starting from the top left corner, how many ways are there to reach the bottom right corner?

You can only move right and down. 0 represents an empty space while 1 represents a wall you cannot walk through.

For example, given the following matrix:

[[0, 0, 1],
 [0, 0, 1],
 [1, 0, 0]]

Return two, as there are only two ways to get to the bottom right:

• Right, down, down, right
• Down, right, down, right

The top left corner and bottom right corner will always be 0

Example:

Input:  matrix = {{0, 0, 1}, {0, 0, 1}, {1, 0, 0}}
Output: 2

Approach

C++

#include <bits/stdc++.h>
using namespace std;

int numberOfWays(vector<vector<int>> &matrix)
{
    int n = matrix.size();
    if (n == 0)
        return 0;
    int m = matrix[0].size();
    int dp[n][m];
    for (int i = 0; i < n; i++)
    {
        if (matrix[i][0] == 1)
        {
            while (i < n)
            {
                dp[i][0] = 0;
                i++;
            }
        }
        else
            dp[i][0] = 1;
    }
    for (int i = 0; i < m; i++)
    {
        if (matrix[0][i] == 1)
        {
            while (i < m)
            {
                dp[0][i] = 0;
                i++;
            }
        }
        else
            dp[0][i] = 1;
    }
    for (int i = 1; i < n; i++)
    {
        for (int j = 1; j < m; j++)
        {
            if (matrix[i][j] == 1)
                dp[i][j] = 0;
            else
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }
    return dp[n - 1][m - 1];
}
int main()
{

    vector<vector<int>> matrix = {{0, 0, 1},
                                  {0, 0, 1},
                                  {1, 0, 0}};

    cout << numberOfWays(matrix) << "\n";

    return 0;
}

Check whether any permutation of string is a palindrome

Given a string, determine whether any permutation of it is a palindrome.

For example, carrace should return true, since it can be rearranged to form racecar, which is a palindrome. daily should return false, since there's no rearrangement that can form a palindrome.

Example:

Input:  str = "carrace"
Output: true

Approach

C++

#include <bits/stdc++.h>
using namespace std;

int main()
{
    string str = "carrace";

    map<char, int> mp;
    for (int i = 0; i < str.size(); i++)
    {
        mp[str[i]]++;
    }

    int cnt = 0;
    for (auto it = mp.begin(); it != mp.end(); it++)
    {
        if (it->second & 1)
            cnt++;
    }
    if (cnt > 1)
        cout << "false\n";
    else
        cout << "true\n";

    return 0;
}

Scoreboard queries

In a tournament there are $(N+1)$ players, $N$ players have already played and their scores are denoted by an array $A$. Here, $A_1$ is the score of the first player, $A_2$ of the second, ..., $A_N$ of the $N^{th}$ player.

Now, the organizers decide the ranks according to the following rules:

The player $x$ scored more than player $y$, player $x$ gets a better rank.

In the case of a tie, the player with lower indices gets a better rank.

Now, it is the turn of the $(N+1{)}^{th}$ player to play. Before playing, he wants to know the number of ranks that he can secure so that he can decide his strategy.

Now, the jury has some scoreboard updates. Therefore, your task is to tell the jury after every update the number of distinct possible ranks that he can get.

Example:

Input:  n = 4, q = 1, arr = {2, 1, 1, 5}

Output:

5

Approach:

C++

#include <bits/stdc++.h>
using namespace std;

void scoreboardQueries(long n, long q, vector<long> v,
                       vector<vector<long>> &queries)
{
    unordered_map<long, long> board;
    for (long i = 1; i <= n; ++i)
    {

        ++board[v[i]];
    }
    for (long i = 0; i < q; i++)
    {
        long l = queries[i][0];
        long r = queries[i][1];
        --board[v[l]];
        if (board[v[l]] == 0)
            board.erase(v[l]);
        v[l] = r;
        ++board[v[l]];
        cout << board.size() + 1 << "\n";
    }
}
int main()
{

    long n = 4, q = 1;
    vector<long> arr = {2, 1, 1, 5};
    vector<long> v(n + 1);
    for (long i = 1; i <= n; i++)
        v[i] = arr[i - 1];
    vector<vector<long>> queries = {{2, 3}};

    scoreboardQueries(n, q, v, queries);

    return 0;
}