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...

Minimum Changes To Make Alternating Binary String

You are given a string s consisting only of the characters '0' and '1'. In one operation, you can change any '0' to '1' or vice versa.

The string is called alternating if no two adjacent characters are equal. For example, the string "010" is alternating, while the string "0100" is not.

Return the minimum number of operations needed to make s alternating

Example :

Input: s = "0100"
Output: 1

Explanation: If you change the last character to '1', s will be "0101", which is alternating 

SOLUTION

int minOperations(string s)

{

    int n = s.length();

    if (n <= 1)

        return 0;

    int c1 = 0;

    int c0 = 0;

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

    {

        if (i % 2)

        {

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

                c0++;

            else

                c1++;

        }

        else

        {

            if (s[i] == '0')

                c0++;

            else

                c1++;

        }

    }

    return min(c0, c1);

}

Thank You...

Next Permutation

Implement the next permutation, which rearranges the list of numbers into Lexicographically next greater permutation of list of numbers. If such arrangement is not possible, it must be rearranged to the lowest possible order i.e. sorted in an ascending order. You are given an list of numbers arr[ ] of size N

Example :

Input: N = 3
arr = {3, 2, 1}
Output: {1, 2, 3}
Explaination: As arr[] is the last permutation. 
So, the next permutation is the lowest one.

Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)

Constraints:

1 ≤ N ≤ 100  

SOLUTION

vector<int> nextPermutation(int n, vector<int> nums)

{

    // code here

    int idx = -1;

    for (int i = n - 1; i > 0; i--)

    {

        if (nums[i] > nums[i - 1])

        {

            idx = i;

            break;

        }

    }

    if (idx == -1)

    {

        reverse(nums.begin(), nums.end());

    }

    else

    {

        int prev = idx;

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

        {

            if (nums[i] > nums[idx - 1] && nums[i] <= nums[prev])

            {

                prev = i;

            }

        }

        swap(nums[idx - 1], nums[prev]);

        reverse(nums.begin() + idx, nums.end());

    }

    return nums;

}

THANK  YOU...Explore Other Programmes Also