Connection Status:
Competition Arena > ValueOfString

ValueOfString

SRM 652 · 2015-01-29 · by lg5293

SRM 652 · 2015-01-29 · by lg5293 · Brute Force
Class Name: ValueOfString
Return Type: int
Method Name: findValue
Arg Types: (string)
Problem Statement

Problem Statement

You are given a String s consisting of lower case letters. We assign the letters 'a' to 'z' values of 1 to 26, respectively. We will denote the value assigned to the letter X by val[X]. For example, val['a'] = 1 and val['e'] = 5.

We define the value of the string s as follows. For each letter s[i], let k[i] be the number of letters in s that are less than or equal to s[i], including s[i] itself. Then, the value of s is defined to be the sum of k[i] * val[s[i]] for all valid i.

Given the string, compute and return the value of the string.

Constraints

  • s will contain between 1 and 50 characters, inclusive.
  • s will consist of lowercase letters ('a'-'z').
Examples
0)
"babca"
Returns: 35

The value of this string is 2*4 + 1*2 + 2*4 + 3*5 + 1*2 = 35. We can get the value as follows. The first character is a 'b' which has value 2, and has 4 characters that are less than or equal to it in the string (i.e. the first, second, third and fifth character of the string). Thus, this first character contributes 2*4 to the sum. We can derive a similar expression for each of the other characters.

1)
"zz"
Returns: 104
2)
"y"
Returns: 25
3)
"aaabbc"
Returns: 47
4)
"topcoder"
Returns: 558

Submissions are judged against all 74 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class ValueOfString with a public method int findValue(string s) · 74 test cases · 2 s / 256 MB per case

Submitting as anonymous