Neat String Question

help
, , ,
1

Question:

Neat String

A neat string is one in which for a particular alphabet (from ‘a’ to ‘z’), the string should contain only its uppercase characters or lowercase characters.

For example, the neat strings for “aAbB” are “aabb”, “AAbb”, “aaBB”, “AABB”.

You are given a string S with size N. The string contains both lowercase and uppercase characters. You can perform one of the following operations on any character of the string any number of times, where each operation has a cost associated with it.

  • Change a character from lowercase to uppercase. Every such operation incurs a cost CU. For eg - changing “yyyy” to “Yyyy” would cost 1 CU.

  • Change a character from uppercase to lowercase. Every such operation incurs a cost CL. For eg - changing “Aaa” to “aaa” would cost 1 CL.

Your task is to convert the given string into a neat string which requires the minimum total cost to build.

Note: If there are multiple neat strings with the same minimum total cost to build, the one among them with the maximum uppercase characters has to be selected.



Input Specification:

input1: a string S
input2: an integer denoting the length of string S
input3: an integer denoting the cost CL i.e., the cost of changing a character to lowercase
input4: an integer denoting the cost CU i.e., the cost of changing a character to uppercase

Output Specification:

Return the Neat string that requires the minimum total cost to build.




Example 1:

input1: aabbAA
input2: 6
input3: 1
input4: 1

Output: AAbbAA

Explanation:
There are 2 Neat strings possible for “aabbAA” with a minimum total cost which are “aabbaa” and “AAbbAA”

The total cost for converting “aabbAA” to “AAbbAA” is 2 as:
Converting “aabbAA” to “aAbbAA” costs 1 CU and,
Further converting “aAbbAA” to “AAbbAA” costs 1 CU so Total cost = 2

And, the total cost for converting “aabbAA” to “aabbaa” is 2 as :
Converting “aabbAA” to “aabbaA” costs 1 CU and,
Further converting “aabbaA” to “aabbaa” costs 1 CU so Total cost = 2

We need to return “AAbbAA” because it has more uppercase characters than “aabbaa”




Example 2:

input1: aAPbBP
input2: 6
input3: 1
input4: 2

Output: aaPbbP

Explanation:
There are 4 Neat strings possible for “aAPbBP” which are - “aaPbbP”, “AAPBBP”, “AAPbbP” and “aaPBBP”.

The answer is “aaPbbP” as it requires a minimum total cost to build which is 2.
“aAPbBP” to “aaPbBP” costs 1 CL
"aaPbBP to “aaPbbP” costs 1 CL, Total cost = 1+1 = 2

2

Why is this tagged DP when we can solve using Greedy technique? :thinking:

3

Fixed it.
Can you please elaborate on how greedy algorithm can be used for it .
Actually I am new to programming and this problem is troubling me for so long

4

This is my approach (hope it works).

  • Let us record the frequency of each character in two different collections.
  • Let’s say countUpper[ch] denotes the number of times alphabet ch occurs in upper case. Similarly, countLower[ch] denotes the number of times alphabet ch occurs in Lower case.
  • Now for each alphabet (from a to z), find if it is optimal to use upper case or lower case. For example, let’s say countUpper[a] is 2 and countLower[a] is 3. Now, let CL and CU be 2. So, to convert all upper case letters of ‘a’ in given string to lower case, the cost is CL * countUpper[a] , viz 4. Similarly, to convert all lower case letters of ‘a’ in given string to upper case, the cost is CU * countLower[a] viz, 6.
    Now, it’s time to decide which conversion costs less. Since converting all characters of ‘a’ in the string from upper case to lower case is cheaper, we do that.
    To remember we converted all characters of any alphabet to upper or lower, we use a boolean array. Simply, result[ch] will be 1 if ch is converted to upper else 0.
  • Now, we need to construct the string. How do we do that?
    Simple, traverse the given string and for each character we encounter, we check if we converted it to lower or upper using result array and append the corresponding character to answer string.

My code in C:

#include <stdio.h>
#include <ctype.h>

#define size 100001

int main() {
    
    // Scan the string
    char s[size];
    scanf("%s", s);
    
    // Scan the length
    int length = 0;
    scanf("%d", &length);
    
    // Scan the costs
    int costToLower, costToUpper;
    scanf("%d %d", &costToLower, &costToUpper);
    
    // Two arrays to record the frequency of each letter
    int upperFreq[26] = {0};
    int lowerFreq[26] = {0};
    
    // Loop that calculates the frequency of each letter
    
    for(int i = 0; i < length; i++) {
        if(isupper(s[i]))
            upperFreq[s[i] - 'A'] ++;
        else
            lowerFreq[s[i] - 'a'] ++;
    }
    
    
    // result[i] = 1 if i is converted to upper else 0
    int result[26] = {0};
    
    for(int i = 0; i < 26; i++) {
        int toUpperCost = lowerFreq[i] * costToUpper;
        int toLowerCost = upperFreq[i] * costToLower;
        
        // if costs of conversion are same, we prefer
        // conversion from lower to upper
        
        if(toUpperCost <= toLowerCost) {
            result[i] = 1;
        }
    }
    
    char answer[size];
    answer[length] = '\0'; // To denote the end of string
    
    
    
    for(int i = 0; i < length; i++) {
        
        answer[i] = (result[tolower(s[i]) - 'a'] ? toupper(s[i]) : tolower(s[i]));
        
        // Depending on the decisions made earlier, we will construct new string
    }
    
    printf("%s", answer);
    
    return 0;
}

It looks like there is a bug in the sample input 2.

Why are there two different strings in input1 and explanation?

5

Thanks for going through all the way to provide the code to the solution.
Yeah, you were right there was a mistype in the input1of example 2 which is now fixed.
Thanks for pointing it out.

1 Like