Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
2.1.
Example
3.
Approach 
3.1.
Algorithm
3.2.
Dry Run
3.3.
Implementation in C++
3.4.
Complexity Analysis
4.
Frequently Asked Questions
4.1.
What is a string?
4.2.
How can you find the length of a string in C++?
4.3.
What is the difference between a character and a string?
4.4.
How can you compare two strings in c++?
4.5.
How to convert a string in uppercase or lowercase in C++?
5.
Conclusion
Last Updated: Mar 27, 2024
Easy

Count Strings that Do Not Contain Any Alphabet’s Both Uppercase and Lowercase

Author Rishabh
0 upvote
gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
Earn badges and level up

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.  

intro image

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 of N 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.

Example

Input

stringArray = {INDIA, AUSTRAlia, Norway, london, USA}

Output

4

Explanation

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.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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

  1. Consider a variable ‘cnt’, initialized to 0, 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. 
     
  2. Initialize an unordered map ‘lowercase_freq’, which will be used to store the frequency of lowercase characters in the current string.
     
  3. 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’.
     
  4. Traverse each of the strings 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. 
     
  5. If the current string is valid, increment ‘cnt’. 
     
  6. This ‘cnt’ will provide us with the final answer, so return it. 

Dry Run

1. Input values:

  • String stringArray = {"INDIA", "AUSTRAlia", "Norway", "london", "USA"}
  • cnt = 0

i

stringArray[i]

lowercase

uppercase

Alphabet with both uppercase and lowercase

Boolean “isAllowed”

cnt

0

“INDIA”

0

5

No lowercase alphabet

Yes

1

1

“AUSTRAlia”

3

6

‘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;
}


Output

image 1

Complexity Analysis

Time Complexity

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:

Recommended problems -

 

To learn more about DSA, competitive coding, and many more knowledgeable topics, please look into the guided paths on Coding Ninjas Studio. Also, you can enrol in our courses and check out the mock test and problems available to you. Please check out our interview experiences and interview bundle for placement preparations.

Happy Coding!

Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass