Do you think IIT Guwahati certified course can help you in your career?
Introduction
Arrays and strings form the backbone of competitive programming and data structures and algorithms. So, it is crucial to have a tight grip on these fundamental topics before implementing and solving complex and more challenging problems.
In this blog, we will discuss one such fundamental and easy problem. So, let's give this a try.
Problem Statement
You have been provided with an array ofN strings. Your task is to determine the string’s count that contains only uppercase characters or only lowercase characters, but not both of an alphabet.
Let us look at a few examples before moving on to its solution.
The second string “AUSTRAlia” contains ‘a’ as both uppercase and lowercase. Hence, the output is 4 because all the strings except the second string contains only uppercase characters or only lowercase characters, but not both of an alphabet.
Approach
One approach we can think of is to iterate through all the provided strings and, for each letter, verify whether the string contains both its lowercase and uppercase versions.
Algorithm
Consider a variable ‘cnt’, initialized to0, that will keep a count of the strings that satisfy the given condition. Initialise a boolean ‘isAllowed’ to true, which will be used to check if the string is valid or not.
Initialize an unordered map ‘lowercase_freq’, which will be used to store the frequency of lowercase characters in the current string.
Traverse the vector of strings and, at each iteration for a stringArray[i], check if the character is lowercase or not. If it is lowercase, increment the frequency in ‘lowercase_freq’.
Traverse each of thestrings again and check if it is uppercase and its lowercase version is present in the string or not. If present, set ‘isAllowed’ to false and break the loop.
If the current string is valid, increment ‘cnt’.
This ‘cnt’ will provide us with the final answer, so return it.
‘A’ is there in both uppercase(‘A’) and lowercase(‘a’)
No
1
2
“Norway”
5
1
‘N’ is not present as lowercase
Yes
2
3
“london”
6
0
No uppercase alphabet
Yes
3
4
“USA”
0
3
No lowercase alphabet
Yes
4
2. From the table, ‘cnt’ increases when a stringArray[i] does not have both uppercase and lowercase alphabet of any stringArray[i].
3. Hence, the output is 4.
Implementation in C++
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
/*
Function to find count of strings that
do not contain the uppercase and
lowercase character of same alphabet
*/
int countStrings( vector<string>& arr){
// Variable to store the answer
int cnt = 0;
// Loop to iterate through the array arr[]
for ( auto& x : arr){
bool isAllowed = true;
// Vector to store the frequency of lowercase characters
unordered_map<char, int> lowercase_freq;
// Iterate through the current string
for (auto& y : x){
if (islower(y)){
lowercase_freq[y]++;
}
}
// Check if any uppercase letter have its lowercase version
for (auto& y : x){
if (isupper(y) && lowercase_freq[tolower(y)] > 0){
isAllowed = false;
break;
}
}
/*
If current string is not a
valid string, increment the count
*/
if (isAllowed){
cnt++;
}
}
// Return answer
return cnt;
}
// Driver code
int main(){
vector<string> arr = {"INDIA", "AUSTRAlia", "Norway", "london", "USA"};
// Call the function and print
cout << countStrings(arr) << endl;
return 0;
}
You can also try this code with Online C++ Compiler
The time complexity is O(N * M), where N is the size of the vector of strings, and M is the length of the longest string. We are traversing all the N strings from the vector and traversing the individual strings completely. Thus, the time complexity is O(N * M).
Space Complexity
The space complexity is O(26*N + M), where N is the size of the vector of strings, and M is the length of the longest string. It is because of the unordered map ‘lowercase_freq’ that stores the frequency of all lowercase characters in the string.
Frequently Asked Questions
What is a string?
A string is a group of characters stored as a variable. It is enclosed in double quotes.
How can you find the length of a string in C++?
You can use the ‘length()’ method of the string class in C++ to find the length of a string. We can also use the ‘size()’ and ‘strlen()’ functions.
What is the difference between a character and a string?
A character is a single symbol or letter, while a string is a sequence of characters.
How can you compare two strings in c++?
You can use the ‘compare()’ method to compare two strings. We can also use operators ‘==’ and ‘!=’ to compare. We can also use ‘strcmp()’ function when using string.
How to convert a string in uppercase or lowercase in C++?
We can convert a string to uppercase or lowercase using the “toupper()” or “tolower()” function in C++.
Conclusion
In this blog, we learned the problem of counting strings that do not contain any alphabet’s, both uppercase and lowercase. We have implemented the problem in C++ programming language.
For more string data structure articles, you can refer following links:
84+ registered 