Sort an array of 0s, 1s and 2s

 Sort an array of 0s, 1s and 2s-Data Structures

 Sort an array of 0s, 1s and 2s-Data Structures

Given an array of size N containing only 0s, 1s, and 2s; sort the array in ascending order

Example :

Input: 
N = 4
arr[] = {0 1 0 2}
Output:
0 0 1 2
Explanation:
0s 1s and 2s are segregated 
into ascending order

Solution:

void sort012(int a[], int n)

{

    

    int low = 0;

    int high = n - 1;

    int mid = 0;

    while (mid <= high)

    {

        if (a[mid] == 0)

        {

            swap(a[low], a[mid]);

            low++;

            mid++;

        }

        else if (a[mid] == 1)

        {

            mid++;

        }

        else

        {

            swap(a[mid], a[high]);

            high--;

        }

    }

}

Thank You.

Count the Reversals

 Count the Reversals- Data Structures and Algorithms

Given a string S consisting only of opening and closing curly brackets '{' and '}' find out the minimum number of reversals required to make a balanced expression

Input
The first line of input contains an integer T, denoting the number of test cases. Then T test cases
follow. The first line of each test case contains a string S consisting only of { and }.

Output
Print out minimum reversals required to make S balanced. If it cannot be balanced, then print -1

Examples
Input
4
}{{}}{{{
{{}}}}
{{}{{{}{{}}{{
{{{{}}}}

Output
3
1
-1
0

Solution:

For better understanding of this code,you should Check Parenthesis Checker

#include <bits/stdc++.h>

using namespace std;

int main()

{

    //code

    int t;

    cin >> t;

    while (t--)

    {

        string s;

        cin >> s;

        if (s.length() % 2 != 0)

            cout << "-1" << endl;

        else

        {

            stack<char> stk;

            int c1 = 0;

            int c2 = 0;

            for (int i = 0; i < s.length(); i++)

            {

                char ch = s[i];

                if (ch == '{')

                {

                    stk.push(ch);

                    c2++;

                }

                else if (ch == '}' and !stk.empty() and stk.top() == '{')

                {

                    stk.pop();

                    c2--;

                }

                else

                {

                    c1++;

                }

            }

            if (c1 % 2 != 0)

                //checking odd even

                c1 = (c1 / 2) + 1;

            //odd then add 1 else remain same

            else

                c1 = c1 / 2;

            if (c2 % 2 != 0)

                //checking odd or even

                c2 = (c2 / 2) + 1;

            //odd then add 1 else remain same

            else

                c2 = c2 / 2;

            cout << c1 + c2 << endl;

        }

    }

    return 0;

}

Convert a sentence into its equivalent mobile numeric keypad sequence

 Convert a sentence into its equivalent mobile numeric keypad sequence-Data Structure and Algorithms

Given a sentence in the form of a string, convert it into its equivalent mobile numeric keypad sequence

Input : STRIVE
Output : 7777877744488833
For obtaining a number, we need to press a
number corresponding to that character for 
number of times equal to position of the 
character. For example, for character C, 
we press number 2 three times and accordingly.

Input : HELLO WORLD
Output : 4433555555666096667775553

Solution:

// #include <iostream>

#include <bits/stdc++.h>

using namespace std;

int main()

{

    // cout<<"Hello World!";

    string s[] = {"2", "22", "222",

                  "3", "33", "333",

                  "4", "44", "444",

                  "5", "55", "555",

                  "6", "66", "666",

                  "7", "77", "777", "7777",

                  "8", "88", "888",

                  "9", "99", "999", "9999"};

    string input;

    cin >> input;

    string ans = "";

    for (int i = 0; i < input.length(); i++)

    {

        if (input[i] == ' ')

            ans += '0';

        else

        {

            int idx = input[i] - 'A';

            ans += s[idx];

        }

    }

    cout << ans << endl;

    return 0;

}

Thank You

Longest Prefix Suffix (KMP Algorithm)

 Longest Prefix Suffix (KMP Algo)

Given a string of characters, find the length of the longest proper prefix which is also a proper suffix.

Example:

Input: s = "abab"
Output: 2
Explanation: "ab" is the longest proper 
prefix and suffix.

Steps:

Make a array to store length of the matching prefix and Suffix  in order that the last entry will have the matched prefix and suffix length.

Solution:

int lps(string s)

{

    vector<int> A(s.size(), 0);

    int j = 0, i = 1;

    while (i < s.size())

    {

        if (s[i] == s[j])

        {

            A[i] = j + 1;

            j++;

            i++;

        }

        else

        {

            if (j == 0)

                i++;

            else

                j = A[j - 1];

        }

    }

    return A.back();

    // back() return last entry of the vector

}

Thank You.

Parenthesis Checker

 Parenthesis Checker

Given an expression string x. Examine whether the pairs and the orders of “{“,”}”,”(“,”)”,”[“,”]” are correct in exp.
For example, the function should return 'true' for exp = “[()]{}{[()()]()}” and 'false' for exp = “[(])”

Example 1:

Input:
{([])}
Output: 
true
Explanation: 
{ ( [ ] ) }. Same colored brackets can form 
balaced pairs, with 0 number of 
unbalanced bracket.

Example 2:

Input: 
()
Output: 
true
Explanation: 
(). Same bracket can form balanced pairs, 
and here only 1 type of bracket is 
present and in balanced way

Solution:

bool ispar(string x)

{

    // Your code here

    stack<char> s;

    for (int i = 0; i < x.size(); i++)

    {

        if (x[i] == '(' || x[i] == '{' || x[i] == '[')

            s.push(x[i]);

        else

        {

            if (s.empty())

                return false;

            char c = s.top();

            if (x[i] == ')' && c != '(')

                return false;

            else if (x[i] == '}' && c != '{')

                return false;

            else if (x[i] == ']' && c != '[')

                return false;

            s.pop();

        }

    }

    return s.empty();

}

Count Number of Homogenous Substrings

 Count Number of Homogenous Substrings- Data Structures and Algorithms-Leetcode Weekly Challenge

Given a string s, return the number of homogenous substrings of s. Since the answer may be too large, return it modulo 109 + 7.

A string is homogenous if all the characters of the string are the same.

A substring is a contiguous sequence of characters within a string

Example:

Input: s = "abbcccaa"
Output: 13
Explanation: The homogenous substrings are listed as below:
"a"   appears 3 times.
"aa"  appears 1 time.
"b"   appears 2 times.
"bb"  appears 1 time.
"c"   appears 3 times.
"cc"  appears 2 times.
"ccc" appears 1 time.
3 + 1 + 2 + 1 + 3 + 2 + 1 = 13.

SOLUTION

int countHomogenous(string s)

{

    long long int num = 1e9 + 7;

    long long int result = 0;

    long long int count = 1;

    for (int i = 1; i < s.size(); i++)

    {

        if (s[i] == s[i - 1])

        {

            count++;

        }

        else

        {

            result += (count * (count + 1)) / 2;

            count = 1;

        }

    }

    result += (count * (count + 1)) / 2;

    result = result % num;

    return result;

}

Thank You...