StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POLatest Codility Time Problems
text
Body
copied!<p>Just got done with the latest Codility, passed it, but didnt get 100% on it</p> <p>Here is the spec</p> <p>A prefix of a string S is any leading contiguous part of S. For example, "c" and "cod" are prefixes of the string "codility". For simplicity, we require prefixes to be non-empty. The product of prefix P of string S is the number of occurrences of P multiplied by the length of P. More precisely, if prefix P consists of K characters and P occurs exactly T times in S, then the product equals K * T.</p> <p>For example, S = "abababa" has the following prefixes:</p> <pre><code>"a", whose product equals 1 * 4 = 4, "ab", whose product equals 2 * 3 = 6, "aba", whose product equals 3 * 3 = 9, "abab", whose product equals 4 * 2 = 8, "ababa", whose product equals 5 * 2 = 10, "ababab", whose product equals 6 * 1 = 6, "abababa", whose product equals 7 * 1 = 7. </code></pre> <p>The longest prefix is identical to the original string. The goal is to choose such a prefix as maximizes the value of the product. In above example the maximal product is 10. In this problem we consider only strings that consist of lower-case English letters (a−z).</p> <p>So basically, it is a string traverse problem. I was able to pass all the validation parts, but I lost on the time. Here is what I wrote</p> <pre><code>int Solution(string S) { int finalCount = 0; for (int i = 0; i <= S.Length - 1; i++) { string prefix = S.Substring(0, i + 1); int count = 0; for (int j = 0; j <= S.Length - 1; j++) { if (prefix.Length + j <= S.Length) { string newStr = S.Substring(j, prefix.Length); if (newStr == prefix) { count++; } } if (j == S.Length - 1) { int product = count * prefix.Length; if (product > finalCount) { finalCount = product; } } } } return finalCount; } </code></pre> <p>I know that the nested loop is killing me, but I cannot think of a way to traverse the "sections" of the string without adding the other loop.</p> <p>Any help would be appreciated.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload