Given an array of strings arr[], containing N strings, the task is to count the number of strings that do not contain both the uppercase and the lowercase character of an alphabet.
Example:
Input: arr[]={ “abcdA”, “abcd”, “abcdB”, “abc” }
Output: 2
Explanation: The first string contains both the uppercase and the lowercase character for alphabet ‘a’. Similarly 3rd string also contains the uppercase and the lowercase character for alphabet ‘b’. Hence the count of valid strings is 2.Input: arr[]={ “xyz”, “abc”, “nmo” }
Output: 3
Approach: The given problem can be solved using a greedy approach by iterating through all the given strings and for each alphabet check if the given string contains both its uppercase and the lowercase counterparts. Follow the below steps to solve this problem:
- Create a variable count to store the required count. Initialize it with 0.
- Now, traverse on each string in array arr[] and for each string store the frequency of its lowercase characters in an unordered map, M.
- Now traverse on that string, and for each uppercase letter check if the frequency of its lowercase counterpart is greater than zero. if it is, then increment the value of count by 1.
- Return count as the final answer.
Below is the implementation of the above approach:
C++
// C++ code for the above approach#include <bits/stdc++.h>using namespace std;// Function to find count of strings that// do not contain the uppercase and// lowercase character of same alphabetint countStrings(vector<string>& arr){ // Variable to store the answer int count = 0; // Loop to iterate through // the array arr[] for (auto x : arr) { bool isAllowed = 1; // Vector to store the frequency // of lowercase characters unordered_map<char, int> M; // Iterator through the // current string for (auto y : x) { if (y - 'a' >= 0 and y - 'a' < 26) { M[y]++; } } for (auto y : x) { // Check if any uppercase letter // have its lowercase version if (y - 'A' >= 0 and y - 'A' < 26 and M[tolower(y)] > 0) { isAllowed = 0; break; } } // If current string is not a valid // string, increment the count if (isAllowed) { count += 1; } } // Return Answer return count;}// Driver Codeint main(){ vector<string> arr = { "abcdA", "abcd", "abcdB", "abc" }; cout << countStrings(arr);} |
Java
// Java code for the above approachimport java.util.*;class GFG{// Function to find count of Strings that// do not contain the uppercase and// lowercase character of same alphabetstatic int countStrings(String[]arr){ // Variable to store the answer int count = 0; // Loop to iterate through // the array arr[] for (String x : arr) { boolean isAllowed = true; // Vector to store the frequency // of lowercase characters HashMap<Character,Integer> M = new HashMap<Character,Integer>(); // Iterator through the // current String for (char y : x.toCharArray()) { if (y - 'a' >= 0 && y - 'a' < 26) { if(M.containsKey(y)){ M.put(y, M.get(y)+1); } else{ M.put(y, 1); } } } for (char y : x.toCharArray()) { // Check if any uppercase letter // have its lowercase version if (y - 'A' >= 0 && y - 'A' < 26 && M.containsKey(Character.toLowerCase(y)) && M.get(Character.toLowerCase(y)) > 0) { isAllowed = false; break; } } // If current String is not a valid // String, increment the count if (isAllowed) { count += 1; } } // Return Answer return count;}// Driver Codepublic static void main(String[] args){ String []arr = { "abcdA", "abcd", "abcdB", "abc" }; System.out.print(countStrings(arr));}}// This code is contributed by 29AjayKumar |
Python3
# Python code for the above approach# Function to find count of strings that# do not contain the uppercase and# lowercase character of same alphabetdef countStrings(arr): # Variable to store the answer count = 0 # Loop to iterate through # the array arr[] for x in arr: isAllowed = 1 # Vector to store the frequency # of lowercase characters M = {} # Iterator through the # current string for y in x: if (ord(y) - ord('a') >= 0 and ord(y) - ord('a') < 26): if(y in M): M[y] += 1 else: M[y] = 1 for y in x: # Check if any uppercase letter # have its lowercase version if (ord(y) - ord('A') >= 0 and ord(y) - ord('A') < 26 and M[y.lower()] > 0): isAllowed = 0 break # If current string is not a valid # string, increment the count if (isAllowed): count += 1 # Return Answer return count# Driver Codearr = ["abcdA", "abcd", "abcdB", "abc"]print(countStrings(arr))# This code is contributed by gfgking. |
C#
// C# code for the above approachusing System;using System.Collections;using System.Collections.Generic;class GFG{ // Function to find count of strings that// do not contain the uppercase and// lowercase character of same alphabetstatic int countStrings(ArrayList arr){ // Variable to store the answer int count = 0; // Loop to iterate through // the array arr[] foreach (string x in arr) { bool isAllowed = true; // To store the frequency // of lowercase characters Dictionary<char, int> M = new Dictionary<char, int>(); // Iterator through the // current string foreach (char y in x) { if (y - 'a' >= 0 && y - 'a' < 26) { if (M.ContainsKey(y)) { M[y] = M[y] + 1; } else { M.Add(y, 1); } } } foreach (char y in x) { // Check if any uppercase letter // have its lowercase version if (y - 'A' >= 0 && y - 'A' < 26 && M[Char.ToLower(y)] > 0) { isAllowed = false; break; } } // If current string is not a valid // string, increment the count if (isAllowed) { count += 1; } } // Return Answer return count;}// Driver Codepublic static void Main(){ ArrayList arr = new ArrayList(); arr.Add("abcdA"); arr.Add("abcd"); arr.Add("abcdB"); arr.Add("abc"); Console.Write(countStrings(arr));}}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript Program to implement // the above approach // Function to find count of strings that // do not contain the uppercase and // lowercase character of same alphabet function countStrings(arr) { // Variable to store the answer let count = 0; // Loop to iterate through // the array arr[] for (let x of arr) { let isAllowed = 1; // Vector to store the frequency // of lowercase characters let M = new Map(); // Iterator through the // current string for (let i = 0; i < x.length; i++) { y = x[i]; if (y.charCodeAt(0) - 'a'.charCodeAt(0) >= 0 && y.charCodeAt(0) - 'a'.charCodeAt(0) < 26) { if (M.has(y)) { M.set(y, M.get(y) + 1); } else { M.set(y, 1); } } } for (i = 0; i < x.length; i++) { y = x[i]; // Check if any uppercase letter // have its lowercase version if (y.charCodeAt(0) - 'A'.charCodeAt(0) >= 0 && y.charCodeAt(0) - 'A'.charCodeAt(0) < 26 && M.get(y.toLowerCase()) > 0) { isAllowed = 0; break; } } // If current string is not a valid // string, increment the count if (isAllowed) { count += 1; } } // Return Answer return count; } // Driver Code let arr = ["abcdA", "abcd", "abcdB", "abc"]; document.write(countStrings(arr)); // This code is contributed by Potta Lokesh </script> |
Output
2
Time Complexity: O(N * M), where M is the length of the longest string
Auxiliary Space: O(1)
Approach:
- Iterate through each string in the array.
- For each string, check if it contains at least one uppercase and one lowercase character using two boolean flags.
- If the string does not contain both uppercase and lowercase characters, increment the count of valid strings.
- Return the count of valid strings.
Steps:
- Initialize a variable count to 0 to keep track of the number of valid strings.
- Loop through each string in the given array.
- For each string, initialize two boolean flags, one for uppercase and one for lowercase.
- Loop through each character in the string and set the corresponding flag to True if an uppercase or lowercase character is found.
- If the string does not contain both uppercase and lowercase characters, increment the count of valid strings.
- Return the count of valid strings.
C++
#include <iostream>#include <vector>#include <string>using namespace std;int count_strings_without_upper_lower(vector<string> arr) { int count = 0; for (string str : arr) { bool has_upper = false; bool has_lower = false; for (char c : str) { if (isupper(c)) { has_upper = true; } else if (islower(c)) { has_lower = true; } if (has_upper && has_lower) { break; } } if (!has_upper || !has_lower) { count++; } } return count;}// Example Usageint main() { vector<string> arr = {"abcdA", "abcd", "abcdB", "abc"}; cout << count_strings_without_upper_lower(arr) << endl; // Output: 2 return 0;} |
Java
import java.util.ArrayList;import java.util.List;public class Main { public static int countStringsWithoutUpperLower(List<String> arr) { int count = 0; for (String str : arr) { boolean hasUpper = false; boolean hasLower = false; for (char c : str.toCharArray()) { if (Character.isUpperCase(c)) { hasUpper = true; } else if (Character.isLowerCase(c)) { hasLower = true; } if (hasUpper && hasLower) { break; } } if (!hasUpper || !hasLower) { count++; } } return count; } // Example Usage public static void main(String[] args) { List<String> arr = new ArrayList<>(); arr.add("abcdA"); arr.add("abcd"); arr.add("abcdB"); arr.add("abc"); System.out.println(countStringsWithoutUpperLower(arr)); // Output: 2 }} |
Python3
def count_strings_without_upper_lower(arr): count = 0 for string in arr: has_upper = False has_lower = False for char in string: if char.isupper(): has_upper = True elif char.islower(): has_lower = True if has_upper and has_lower: break else: count += 1 return count# Example Usagearr = ["abcdA", "abcd", "abcdB", "abc"]print(count_strings_without_upper_lower(arr)) # Output: 2 |
C#
using System;using System.Collections.Generic;class Program{ // Function to count strings that don't contain both uppercase and lowercase letters static int CountStringsWithoutUpperLower(List<string> arr) { int count = 0; // Initialize a counter to keep track of valid strings foreach (string str in arr) // Iterate through the list of strings { bool hasUpper = false; // Initialize a flag to check for uppercase letters bool hasLower = false; // Initialize a flag to check for lowercase letters foreach (char c in str) // Iterate through the characters in the current string { if (Char.IsUpper(c)) // Check if the character is an uppercase letter { hasUpper = true; // Set the flag to true if an uppercase letter is found } else if (Char.IsLower(c)) // Check if the character is a lowercase letter { hasLower = true; // Set the flag to true if a lowercase letter is found } if (hasUpper && hasLower) { break; // If both uppercase and lowercase letters are found, exit the loop } } if (!hasUpper || !hasLower) // If either uppercase or lowercase letter is missing { count++; // Increment the counter, as the string is valid based on the criteria } } return count; // Return the count of valid strings } static void Main(string[] args) { List<string> arr = new List<string> { "abcdA", "abcd", "abcdB", "abc" }; Console.WriteLine(CountStringsWithoutUpperLower(arr)); // Output: 2 }} |
Javascript
function countStringsWithoutUpperLower(arr) { let count = 0; // Initialize a counter to keep track of valid strings for (let str of arr) { // Iterate through the array of strings let hasUpper = false; // Initialize a flag to check for uppercase letters let hasLower = false; // Initialize a flag to check for lowercase letters for (let c of str) { // Iterate through the characters in the current string if (c.toUpperCase() === c) { // Check if the character is an uppercase letter hasUpper = true; // Set the flag to true if an uppercase letter is found } else if (c.toLowerCase() === c) { // Check if the character is a lowercase letter hasLower = true; // Set the flag to true if a lowercase letter is found } if (hasUpper && hasLower) { break; // If both uppercase and lowercase letters are found, exit the loop } } if (!hasUpper || !hasLower) { // If either uppercase or lowercase letter is missing count++; // Increment the counter, as the string is valid based on the criteria } } return count; // Return the count of valid strings}// Test caseconst arr = ["abcdA", "abcd", "abcdB", "abc"];console.log(countStringsWithoutUpperLower(arr)); // Output: 2 |
Output
2
Time Complexity: O(N*M) where N is the length of the array and M is the length of the longest string in the array.
Auxiliary Space: O(1)
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!
