Saturday, July 9, 2022
HomeWordPress DevelopmentParity of rely of letters whose place and frequency have identical parity

Parity of rely of letters whose place and frequency have identical parity


View Dialogue

Enhance Article

Save Article

Like Article

Given a string S of lowercase English characters, discover out whether or not the variety of the letters whose frequencies within the string have the identical parity as their positions within the English alphabet is odd and even (i.e., they’ve an odd frequency within the string and their place is at an odd quantity within the English alphabet or have even frequency and their place is at a good quantity within the English alphabet).

Examples:

Enter: S = “abbbcc”
Output: ODD
Rationalization: ‘a’ occupies 1st place(odd) in English alphabets and its frequency is odd(1),  
‘b’ occupies 2nd place(even) however its frequency is odd(3) so it doesn’t get counted 
‘c’ occupies third place(odd) however its frequency is even(2) so it additionally doesn’t get counted.

Enter: S = “nobitaa”
Output: EVEN

 

Method: The issue will be solved following the under concept: 

Retailer frequency of every character in a brand new array. Then traverse on that array. Whereas traversing if place of factor is even and its frequency can also be even then increment or if place of factor is odd and its frequency can also be odd then increment the rely and discover the parity of the ultimate rely.

Comply with the steps talked about right here to implement the thought:

  • Create a hash array of dimension 27 (to retailer the frequencies of all of the lowercase characters).
  • Create variables x = 0 and y = 0.
  • Traverse on a string and retailer frequency of every character( S[i] – ‘a’ + 1) in hash array.
  • Traverse on hash array:
    • If the frequency of the character is bigger than 0 then verify if the index is even and its frequency can also be even then increment x,
    • If the index is odd and its frequency can also be odd then increment y.
  • if x + y is even then return even. In any other case, return odd.

Under is the implementation of the above strategy.

C++

  

#embody <bits/stdc++.h>

utilizing namespace std;

  

string oddEven(string S)

{

    

    int hash[27] = { 0 };

    int x = 0, y = 0;

  

    for (int i = 0; i < S.dimension(); i++) {

        hash[S[i] - 'a' + 1]++;

    }

  

    

    for (int i = 1; i < 26; i++) {

        if (hash[i] != 0) {

            if (i % 2 == 0 && hash[i] % 2 == 0)

                x++;

            else if (i % 2 == 1 && hash[i] % 2 == 1)

                y++;

        }

    }

  

    if ((x + y) % 2 == 1)

        return "ODD";

    else

        return "EVEN";

}

  

int principal()

{

    string S = "abbbcc";

  

    

    cout << oddEven(S);

    return 0;

}

Time Complexity: O(|S|) the place |S| is the dimensions of string S.
House Complexity: O(1)

RELATED ARTICLES

LEAVE A REPLY

Please enter your comment!
Please enter your name here

- Advertisment -
Google search engine

Most Popular

Recent Comments