StringMemory | Topcoder Archive

Problem Statement

In many languages strings are represented by immutable data structures. This means that the location where the string contents are stored in memory may not be altered. In some situations, this leads to a large number of similar strings being stored and wasting memory. In this problem, you will consider the situation where each String in s needs to be stored in memory. However, to save space, if one String is a substring of another one, you may forego storing the shorter String in memory. Instead, you may simply store the offset and length of the shorter String. For example, if given {"abcde","bcd"}, only the first String, "abcde", needs to be stored. The second String may be stored as (1,3) - the offset and length of "bcd" in "abcde". If a number of Strings are identical, at least one copy must be stored, while the rest may be stored as an offset and length. For our purposes, storing a String in memory requires a single byte for each character in the String, plus 1 extra byte to terminate the String (this is the case if they are stored with a null terminator). Storing an offset and length, on the other hand, requires exactly 12 bytes. Given these specs, and s, determine the fewest number of bytes required to store all of the Strings in memory. Keep in mind that it sometimes requires fewer bytes to store the actual String than it does to store an offset and length.

Definition

Class:: StringMemory
Method:: byteCount
Parameters:: String[]
Returns:: int
Method signature:: int byteCount(String[] s)
(be sure your method is public)

Notes

You may only store strings that exist in s, even when you might save bytes by storing other strings.

Constraints

s will contain between 1 and 50 elements, inclusive.
Each element of s will contain between 0 and 50 characters, inclusive.
Each character in s will be a lowercase letter ('a'-'z').

Examples

```
{"abcde","abc"}
```
```
Returns: 10
```
In this case it is best to store both Strings in memory as they are. This requires a total of 6 + 4 = 10 bytes.
```
{"abcdabcdabcdabcd","abcdabcdabcdabcd","abcdabcdabcdabcd"}
```
```
Returns: 41
```
"abcdabcdabcdabcd" must be stored in memory once, requiring 17 bytes. The other two copies may be stored as (0,16), each requiring 12 bytes. This gives a total of 17+12+12=41 bytes.
```
{"abcdefghijkl","abcdefghijklm","abcdefghijklmn"}
```
```
Returns: 39
```
If we only store the longest String in its entirety, we require 15+12+12=39 bytes.

{"qwertyuiopasdfghjklzxcvbnm","abcdefghijklmnopqrstuvwxyz"}

Returns: 54

```
{""}
```
```
Returns: 1
```
```
{"abcdefghijkl","abcdefghijkl","abcdefghijklmn","bcdefghijklmno"}
```
```
Returns: 54
```
There are two copies of "abcdefghijkl", but neither of them need to be stored, as they are both substrings of the longer "abcdefghijklmn".

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.