Given a string “str” consisting of lowercase alphabets, the task is to find the minimum number of operations to be applied on string “str” such that all letters of the string “str” are the same. In one operation you can either remove all even indexed letters or you can remove all odd indexed characters.
Examples:
Input: str = “cbcdce”
Output: 1
Explanation: After removing all odd-indexed letters we are left with the string “ccc” in which all the characters are the same. Hence number of operations required is 1.Input: str = “abacaaba”
Output: 2
Explanation: First removing all odd-indexed elements we are left with the string “aaab”. Now again removing odd – indexed elements we have the string “aa”. Hence number of operations required is 2.
Approach: The idea is to use the concept of recursion.
Follow the steps below to solve the problem:
- If all characters in the string are the same then return 0.
- Here we have two choices, we can either remove all odd indexed elements or even indexed elements and simply this can be done by recursion.
- In 1 operation remove all even indexed elements and solve for the remaining string.
- Similarly, remove all odd-indexed elements and solve for the remaining string.
- Return the minimum of above 2.
Below is the code implementation of the above approach:
C++
#include <iostream>#include <string>bool AllCharsAreSame(const std::string& arr){ char ch = arr[0]; for (int i = 1; i < arr.length(); i++) { if (arr[i] != ch) return false; } return true;}int solve(std::string& s){ // If all characters of string are // same then simply answer is zero if (AllCharsAreSame(s)) return 0; // Generate the new strings by removing // either odd indexed or even indexed elements std::string sb1, sb2; for (int i = 0; i < s.length(); i++) { if (i % 2 == 0) { sb1 += s[i]; } else { sb2 += s[i]; } } // Recursively solve for subproblems // generated and compute the result using their answers return 1 + std::min(solve(sb1), solve(sb2));}int main(){ std::string s = "abacaaba"; std::cout << solve(s) << std::endl; return 0;} |
Java
// Java code to implement above approachimport java.io.*;import java.util.*;public class GFG { public static void main(String[] args) { // Scanner scn=new Scanner(System.in); // String s = scn.next(); String s = "abacaaba"; StringBuilder sb = new StringBuilder(s); System.out.println(solve(sb)); } static int solve(StringBuilder s) { // If all characters of string are // same then simply answer is zero if (AllCharsAreSame(s)) return 0; // Generate the new strings by removing // either odd indexed or even // indexed elements StringBuilder sb1 = new StringBuilder(); StringBuilder sb2 = new StringBuilder(); for (int i = 0; i < s.length(); i++) { if (i % 2 == 0) { sb1.append(s.charAt(i) + ""); } else { sb2.append(s.charAt(i) + ""); } } // Recursively solve for subproblems // generated and computing the // result using their answers return 1 + Math.min(solve(sb1), solve(sb2)); } // Function to check in a string all // characters are same or not static boolean AllCharsAreSame(StringBuilder arr) { char ch = arr.charAt(0); for (int i = 1; i < arr.length(); i++) { if (arr.charAt(i) != ch) return false; } return true; }} |
Python
# Function to check if all characters in the string are the samedef all_chars_are_same(arr): ch = arr[0] for i in range(1, len(arr)): if arr[i] != ch: return False return True# Recursive function to solve the problemdef solve(s): # If all characters of the string are the same, the answer is zero if all_chars_are_same(s): return 0 # Generate new strings by removing either odd-indexed or even-indexed elements sb1 = "" sb2 = "" for i in range(len(s)): if i % 2 == 0: sb1 += s[i] else: sb2 += s[i] # Recursively solve for subproblems generated and compute the result using their answers return 1 + min(solve(sb1), solve(sb2))s = "abacaaba"print(solve(s)) |
C#
using System;public class Program{ public static bool AllCharsAreSame(string arr) { char ch = arr[0]; for (int i = 1; i < arr.Length; i++) { if (arr[i] != ch) return false; } return true; } public static int Solve(string s) { // If all characters of string are // same then simply answer is zero if (AllCharsAreSame(s)) return 0; // Generate the new strings by removing // either odd indexed or even indexed elements string sb1 = "", sb2 = ""; for (int i = 0; i < s.Length; i++) { if (i % 2 == 0) { sb1 += s[i]; } else { sb2 += s[i]; } } // Recursively solve for subproblems // generated and compute the result using their answers return 1 + Math.Min(Solve(sb1), Solve(sb2)); } public static void Main() { string s = "abacaaba"; Console.WriteLine(Solve(s)); }}// This code is contributed by Tapesh(tapeshdua420) |
Javascript
// Function to check if all characters in the string are the samefunction allCharsAreSame(arr) { const ch = arr[0]; for (let i = 1; i < arr.length; i++) { if (arr[i] !== ch) return false; } return true;}// Recursive function to solve the problemfunction solve(s) { // If all characters of the string are the same, the answer is zero if (allCharsAreSame(s)) return 0; // Generate new strings by removing either odd-indexed or even-indexed elements let sb1 = ""; let sb2 = ""; for (let i = 0; i < s.length; i++) { if (i % 2 === 0) { sb1 += s[i]; } else { sb2 += s[i]; } } // Recursively solve for subproblems generated and compute the result using their answers return 1 + Math.min(solve(sb1), solve(sb2));}const s = "abacaaba";console.log(solve(s)); |
Output
2
Time Complexity: O(N*log(N)), T(n) = 2*T(n/2) + 2O(n) now using master’s theorem time complexity comes out to be O(Nlog(N)).
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
