Entering edit mode

Click here to Practice

Submit Problem to OJ

Given an array of strings, all but one will have a similar pattern of distances between character values. One will have a different pattern, the odd one out.

**Example**

Given *series* = *['ACB', 'BDC', 'CED', 'DEF']*, the distances for ACB, BDC and CE are (2, -1). For DEF, the distances are (1, 1) so it is the odd one out.

**Function Description**

Complete the functino *findOdd* in the editor below.

*findOdd* has the following parameter(s): *string series[n]*: an array of strings

**Returns**

*string*: the odd one out

**Constraints**

- 3 <= n <= 26
- 2 <= length of element <= 26
- All strings contain only uppercase English letters ascii[A-Z]
- All strings in a single test case will be the same length

Click here to Practice

Submit Problem to OJ

Find the minimum number of operations required to make a string 'similar'.

A String is similar if the number of vowels equals the number of consonants.

A character can be increased or decreased only once at a time.

'a' cannot be decremented and 'z' cannot be incremented further.

**Example 1**:

**Input:** abcd

**Operation**: 1

**Explanation:** Decrement b to a and hence aacd

**Example 2**:

**Input:** bigbangt

**Operations**: 2

**Explanation:** First change one 'b' and the next iteration change next 'b'

Entering edit mode

**Overview**

- Given an array of strings, except one string everyone will have a similar pattern of distances between character values.
- Find that odd one string.

**Solution**

- Since the number of strings and length of each string is very small, we can apply a brute force method.
- We will create a vector for each string that contains the distances between its character.
- Now we will take a single string and compare its vector with every other vector.
- If
**it does not match with any of the other vectors**then the**answer is the current string**else the**answer is the string whose vector does not match with its vector**(that is the vector of the string we have taken).

**Code**

```
ll n;
cin >> n;
vector<string> vs;
for (ll i = 0; i < n; i++)
{
string s;
cin >> s;
vs.pb(s);
}
vector<vector<ll>> vcmp;
for (ll i = 0; i < n; i++)
{
vector<ll> tmp;
ll sz = vs[i].size();
for (ll j = 1; j < sz; j++)
{
tmp.pb(vs[i][j] - vs[i][j - 1]);// push all the distances in a vector
}
vcmp.pb(tmp);// push vector of all strings in a vector let's say vcmp
}
ll tot = 0;
ll idx = -1;
for (ll i = 1; i < n; i++)// now compare vector of 1st string to the vector's of rest of string
{
ll cnt = 0;
for (ll j = 0; j < vcmp[i].size(); j++)
{
if (vcmp[0][j] == vcmp[i][j])// if the distances match increment the count
cnt++;
}
if (cnt == vcmp[i].size())// if every distance match then increment the total
{
tot++;
}
else
{
idx = i;// if every distance does not match then find the index of string with whom it does not match
}
}
if (tot == 0)// If total is zero then answer is the first string
{
cout << vs[0] << endl;
}
else
{
cout << vs[idx] << endl;// the answer is the string at index idx
}
return;
```

Entering edit mode

**Question 2**

`Approach:`

- Precompute the minimum number of operations needed for every alphabet to change its type(vowel/consonant).
- Find the count of vowels and consonants in the given string.
- If
`count(vowels) = count(consonant)`

,`ans = 0`

. - Else, if the count of one type is higher by a count of
`X.`

- Ans = Sum of least
`X/2`

characters of that type in the given string, based on number of operations needed to change its type.

- Ans = Sum of least

`Pseudocode:`

```
bool vowel[26];
vector<int> operation(26, 26);
void findOperation()
{
for (int i = 0; i < 26; i++)
for (int j = i + 1; j < 26; j++)
if (vowel[i] != vowel[j])
{
operation[i] = min(operation[i], j - i);
break;
}
for (int i = 25; i >= 0; i--)
for (int j = i - 1; j >= 0; j--)
if (vowel[i] != vowel[j])
{
operation[i] = min(operation[i], i - j);
break;
}
}
int main()
{
vowel['a' - 'a'] = true;
vowel['e' - 'a'] = true;
vowel['i' - 'a'] = true;
vowel['o' - 'a'] = true;
vowel['u' - 'a'] = true;
findOperation();
string s;
cin >> s;
int ans = 0;
vector<int> vow, con;
for (int i = 0; i < s.size(); i++)
{
if (vowel[s[i] - 'a'])
vow.push_back(operation[s[i] - 'a']);
else
con.push_back(operation[s[i] - 'a']);
}
sort(vow.begin(), vow.end());
sort(con.begin(), con.end());
int X = vow.size() - con.size();
if (X > 0)
for (int i = 0; i < (X / 2); i++)
ans += vow[i];
else
for (int i = 0; i < (-X / 2); i++)
ans += con[i];
cout << ans << endl;
}
```

Loading Similar Posts