Min. operations required so that no two vowels or consonants are adjacent
Given a string S of size N. In one operation you can replace any character of the string with any other character, the task is to find the minimum number of operations required so that no two vowels or consonants are adjacent.
Examples:
Input: N = 4, S = ‘wlrb’
Output: 2
Explanation: We can replace w and r with a.Input: N = 3, S = ‘owf’
Output: 1
Explanation: We can replace f with o.
Approach: This can be solved with the following idea:
It is always optimal to keep vowels and consonent alternatively. So, keep checking whether at even and odd index consonent and vowel are present there. Keep a count of that.
Below are the steps involved:
- Iterate in string s:
- If vowel, convert it to ‘1’.
- If consonebt, convert it to ‘0’.
- First check:
- If even index is having consonent, increment cnt1.
- If odd index is having vowel, increment cnt1.
- Second check:
- If even index is having vowel, increment cnt2.
- If odd index is having consonent, increment cnt2.
- Return min(cnt1, cnt2).
Below is the implementation of the code:
C++
// C++ Implementation #include <bits/stdc++.h> #include <iostream> using namespace std; // Function to find whether it is vowel // or consonent int check( char crr) { // If vowel if (crr == 'a' || crr == 'e' || crr == 'i' || crr == 'o' || crr == 'u' ) return 1; return 0; } // Function to find minimum operations required int solve( int n, string s) { // Iterate in string for ( int i = 0; i < n; i++) { // Check for vowel and consonent if (check(s[i]) == 1) s[i] = '1' ; else s[i] = '0' ; } int cnt1 = 0; // Check if vowel at even indexes and // consonent at odd indexes for ( int i = 0; i < n; i++) { if (i % 2 == 0 && s[i] != '1' ) cnt1++; if (i % 2 == 1 && s[i] != '0' ) cnt1++; } int cnt2 = 0; // Check if vowel at odd indexes and // consonent at even indexes for ( int i = 0; i < n; i++) { if (i % 2 == 0 && s[i] != '0' ) cnt2++; if (i % 2 == 1 && s[i] != '1' ) cnt2++; } // Return the minimum number of operations return min(cnt1, cnt2); } // Driver code int main() { int n = 4; string s = "abcd"; // Function call cout << solve(n, s); return 0; } |
Java
import java.util.Scanner; public class Main { // Function to find whether it is vowel // or consonant static int check( char crr) { // If vowel if (crr == 'a' || crr == 'e' || crr == 'i' || crr == 'o' || crr == 'u' ) return 1 ; return 0 ; } // Function to find minimum operations required static int solve( int n, String s) { // Iterate in string for ( int i = 0 ; i < n; i++) { // Check for vowel and consonant if (check(s.charAt(i)) == 1 ) s = s.substring( 0 , i) + '1' + s.substring(i + 1 ); else s = s.substring( 0 , i) + '0' + s.substring(i + 1 ); } int cnt1 = 0 ; // Check if vowel at even indexes and // consonant at odd indexes for ( int i = 0 ; i < n; i++) { if (i % 2 == 0 && s.charAt(i) != '1' ) cnt1++; if (i % 2 == 1 && s.charAt(i) != '0' ) cnt1++; } int cnt2 = 0 ; // Check if vowel at odd indexes and // consonant at even indexes for ( int i = 0 ; i < n; i++) { if (i % 2 == 0 && s.charAt(i) != '0' ) cnt2++; if (i % 2 == 1 && s.charAt(i) != '1' ) cnt2++; } // Return the minimum number of operations return Math.min(cnt1, cnt2); } // Driver code public static void main(String[] args) { int n = 4 ; String s = "abcd" ; // Function call System.out.println(solve(n, s)); } } // This code is contributed by akshitaguprzj3 |
Python3
# Python Implementation: def check(crr): # If vowel if crr = = 'a' or crr = = 'e' or crr = = 'i' or crr = = 'o' or crr = = 'u' : return 1 return 0 def solve(n, s): # Convert vowels to '1' and consonants to '0' s = [ str (check(c)) for c in s] cnt1 = 0 cnt2 = 0 # Check if vowel at even indexes and consonant at odd indexes for i in range (n): if i % 2 = = 0 and s[i] ! = '1' : cnt1 + = 1 if i % 2 = = 1 and s[i] ! = '0' : cnt1 + = 1 # Check if vowel at odd indexes and consonant at even indexes for i in range (n): if i % 2 = = 0 and s[i] ! = '0' : cnt2 + = 1 if i % 2 = = 1 and s[i] ! = '1' : cnt2 + = 1 # Return the minimum number of operations return min (cnt1, cnt2) n = 4 s = "abcd" # Function call print (solve(n, s)) # This code is contributed by Sakshi |
C#
using System; class Program { // Function to find whether it is a vowel or consonant static int Check( char crr) { // If vowel if (crr == 'a' || crr == 'e' || crr == 'i' || crr == 'o' || crr == 'u' ) return 1; return 0; } // Function to find minimum operations required static int Solve( int n, string s) { // Iterate in the string for ( int i = 0; i < n; i++) { // Check for vowel and consonant if (Check(s[i]) == 1) s = s.Substring(0, i) + '1' + s.Substring(i + 1); else s = s.Substring(0, i) + '0' + s.Substring(i + 1); } int cnt1 = 0; // Check if vowel at even indexes and consonant at odd indexes for ( int i = 0; i < n; i++) { if (i % 2 == 0 && s[i] != '1' ) cnt1++; if (i % 2 == 1 && s[i] != '0' ) cnt1++; } int cnt2 = 0; // Check if vowel at odd indexes and consonant at even indexes for ( int i = 0; i < n; i++) { if (i % 2 == 0 && s[i] != '0' ) cnt2++; if (i % 2 == 1 && s[i] != '1' ) cnt2++; } // Return the minimum number of operations return Math.Min(cnt1, cnt2); } // Driver code static void Main() { int n = 4; string s = "abcd" ; // Function call Console.WriteLine(Solve(n, s)); } } |
Javascript
function check(crr) { // If vowel if (crr === 'a' || crr === 'e' || crr === 'i' || crr === 'o' || crr === 'u' ) { return 1; } return 0; } function solve(n, s) { // Convert vowels to '1' and consonants to '0' s = s.split( '' ).map(c => check(c).toString()); let cnt1 = 0; let cnt2 = 0; // Check if vowel at even indexes and consonant at odd indexes for (let i = 0; i < n; i++) { if (i % 2 === 0 && s[i] !== '1' ) { cnt1 += 1; } if (i % 2 === 1 && s[i] !== '0' ) { cnt1 += 1; } } // Check if vowel at odd indexes and consonant at even indexes for (let i = 0; i < n; i++) { if (i % 2 === 0 && s[i] !== '0' ) { cnt2 += 1; } if (i % 2 === 1 && s[i] !== '1' ) { cnt2 += 1; } } // Return the minimum number of operations return Math.min(cnt1, cnt2); } const n = 4; const s = "abcd" ; // Function call console.log(solve(n, s)); |
Output
1
Time Complexity: O(N)
Auxiliary Space: O(1)