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.
For example, S = "abababa" has the following prefixes:
- "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.
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).
Write a function
class Solution { public int solution(string S); }
that, given a string S consisting of N characters, returns the maximal product of any prefix of the given string. If the product is greater than 1,000,000,000 the function should return 1,000,000,000.
For example, for a string:
- S = "abababa" the function should return 10, as explained above,
- S = "aaa" the function should return 4, as the product of the prefix "aa" is maximal.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [1..300,000];
- string S is made only of lowercase letters (a−z).
using System;
class Solution {
private const int Limit = 1000000000;
public int solution(string S)
{
if (S == null)
throw new ArgumentNullException("S");
int length = S.Length;
if (length < 1 || length > 300000)
throw new ArgumentOutOfRangeException("S");
// Find the maximum match at any given point
int[] matches = BuildMatchTable(S.ToCharArray());
// How many are there of each number?
int maximumCount = matches[0];
var counts = new long[maximumCount + 1];
for (int i = 0; i < length; i++)
counts[matches[i]]++;
// A three counts as a two and a one also
// Update the counts accordingly
for (int i = counts.Length - 2; i >= 0; i--)
counts[i] += counts[i + 1];
// Calculate the products and find the maximum product
long maximumProduct = 0;
for (int i = 0; i < counts.Length; i++)
{
counts[i] *= i;
if (counts[i] > maximumProduct)
maximumProduct = (int)counts[i];
}
if (maximumProduct > Limit)
return Limit;
return (int)maximumProduct;
}
// We only care about matches with the start of the string
public int[] BuildMatchTable(char[] chars)
{
int length = chars.Length;
// A number in this array represents how many characters from that
// point match with the start of the string
var matches = new int[length];
// Left and right boundary of last match
int left = -1;
int right = -1;
// The array matches itself
matches[0] = length;
for (int i = 1; i < length; i++)
{
// If we are not currently in a match...
if (i > right)
{
// Look for a match with the start of the string
int j = 0;
while (j + i < length && chars[j] == chars[j + i])
j++;
// If a match was found, record the length of the match
if (j > 0)
{
matches[i] = j;
left = i;
right = j + i - 1;
}
}
else // We are in a match already discovered
{
// This sequence has already been checked, so we can assign
// matches[i - left] to matches[i]
matches[i] = matches[i - left];
// However, if there is match in that location that goes
// beyond the boundary of the match we're in...
if (i + matches[i] > right)
{
// Check to see how much of it matches into unchecked
// territory and possibly extend it
int j = right + 1;
while (j < length && chars[j - i] == chars[j])
j++;
// Record the updated match
matches[i] = j - i;
left = i;
right = j - 1;
}
}
}
return matches;
}
}
using System;
class Solution {
private const int Limit = 1000000000;
public int solution(string S)
{
if (S == null)
throw new ArgumentNullException("S");
int length = S.Length;
if (length < 1 || length > 300000)
throw new ArgumentOutOfRangeException("S");
// Find the maximum match at any given point
int[] matches = BuildMatchTable(S.ToCharArray());
// How many are there of each number?
int maximumCount = matches[0];
var counts = new long[maximumCount + 1];
for (int i = 0; i < length; i++)
counts[matches[i]]++;
// A three counts as a two and a one also
// Update the counts accordingly
for (int i = counts.Length - 2; i >= 0; i--)
counts[i] += counts[i + 1];
// Calculate the products and find the maximum product
long maximumProduct = 0;
for (int i = 0; i < counts.Length; i++)
{
counts[i] *= i;
if (counts[i] > maximumProduct)
maximumProduct = (int)counts[i];
}
if (maximumProduct > Limit)
return Limit;
return (int)maximumProduct;
}
// We only care about matches with the start of the string
public int[] BuildMatchTable(char[] chars)
{
int length = chars.Length;
// A number in this array represents how many characters from that
// point match with the start of the string
var matches = new int[length];
// Left and right boundary of last match
int left = -1;
int right = -1;
// The array matches itself
matches[0] = length;
for (int i = 1; i < length; i++)
{
// If we are not currently in a match...
if (i > right)
{
// Look for a match with the start of the string
int j = 0;
while (j + i < length && chars[j] == chars[j + i])
j++;
// If a match was found, record the length of the match
if (j > 0)
{
matches[i] = j;
left = i;
right = j + i - 1;
}
}
else // We are in a match already discovered
{
// This sequence has already been checked, so we can assign
// matches[i - left] to matches[i]
matches[i] = matches[i - left];
// However, if there is match in that location that goes
// beyond the boundary of the match we're in...
if (i + matches[i] > right)
{
// Check to see how much of it matches into unchecked
// territory and possibly extend it
int j = right + 1;
while (j < length && chars[j - i] == chars[j])
j++;
// Record the updated match
matches[i] = j - i;
left = i;
right = j - 1;
}
}
}
return matches;
}
}
using System;
class Solution {
private const int Limit = 1000000000;
public int solution(string S)
{
if (S == null)
throw new ArgumentNullException("S");
int length = S.Length;
if (length < 1 || length > 300000)
throw new ArgumentOutOfRangeException("S");
// Find the maximum match at any given point
int[] matches = BuildMatchTable(S.ToCharArray());
// How many are there of each number?
int maximumCount = matches[0];
var counts = new long[maximumCount + 1];
for (int i = 0; i < length; i++)
counts[matches[i]]++;
// A three counts as a two and a one also
// Update the counts accordingly
for (int i = counts.Length - 2; i >= 0; i--)
counts[i] += counts[i + 1];
// Calculate the products and find the maximum product
long maximumProduct = 0;
for (int i = 0; i < counts.Length; i++)
{
counts[i] *= i;
if (counts[i] > maximumProduct)
maximumProduct = (int)counts[i];
}
if (maximumProduct > Limit)
return Limit;
return (int)maximumProduct;
}
// We only care about matches with the start of the string
public int[] BuildMatchTable(char[] chars)
{
int length = chars.Length;
// A number in this array represents how many characters from that
// point match with the start of the string
var matches = new int[length];
// Left and right boundary of last match
int left = -1;
int right = -1;
// The array matches itself
matches[0] = length;
for (int i = 1; i < length; i++)
{
// If we are not currently in a match...
if (i > right)
{
// Look for a match with the start of the string
int j = 0;
while (j + i < length && chars[j] == chars[j + i])
j++;
// If a match was found, record the length of the match
if (j > 0)
{
matches[i] = j;
left = i;
right = j + i - 1;
}
}
else // We are in a match already discovered
{
// This sequence has already been checked, so we can assign
// matches[i - left] to matches[i]
matches[i] = matches[i - left];
// However, if there is match in that location that goes
// beyond the boundary of the match we're in...
if (i + matches[i] > right)
{
// Check to see how much of it matches into unchecked
// territory and possibly extend it
int j = right + 1;
while (j < length && chars[j - i] == chars[j])
j++;
// Record the updated match
matches[i] = j - i;
left = i;
right = j - 1;
}
}
}
return matches;
}
}
The solution obtained perfect score.