I am trying to learn how to write more efficient code. Any chance that some of you ingenious developers can help me and let me know where my code goes wrong? How can I make it more efficient?
I just completed the task at Codility.com and I went through all the tests, but my code was not efficient enough when large lines were passed.
Description of the task:
The string prefix S is any major adjacent part of S. For For example, "c" and "cod" are prefixes of the string "codility". For simplicity, we require prefixes to be non-empty. The product of the prefix P of the string S is the number of occurrences of P multiplied by the length of P. More precisely, if the prefix P consists of K characters and P has exactly T times S, then the product is K * T.
For example, S = "abababa" has the following prefixes:
"a" whose product is 1 * 4 = 4,
"ab" whose product is 2 * 3 = 6,
"aba" whose product is 3 * 3 = 9,
"abab" whose product is 4 * 2 = 8,
"ababa" whose product is 5 * 2 = 10,
"ababab" whose product is 6 * 1 = 6,
"abababa" whose product is 7 * 1 = 7.
The longest prefix is identical to the original line. The goal is to choose a prefix that maximizes the value of the product. In the above example, the maximum product is 10.
In this problem, we will only consider strings consisting of lowercase English letters (az).
Write function
class Solution { public int solution(String S); }
which, given the string S, consisting of N characters, returns the maximum product of any prefix of the string. If the product exceeds 1,000,000,000, the function should return 1,000,000,000.
For example, for a line:
S = "abababa" function should return 10, as explained above,
S = "aaa" function should return 4, as the product of the prefix "aa" is the maximum.
Let's pretend that:
N is an integer in the range [1..300.000];
string S consists only of lowercase letters (az).
Complexity:
Expected Worst Time Complexity - O (N);
The expected worst-case complexity of the space is O (N) (not counting the storage required for the input arguments).
Here are my unsuccessful results:
easy_morphism a → a? a 2.150 s. ERROR TIMEOUT operating time:> 2.15 s. large_random_string loop + random line 1.180 s. TIME ERROR operating time:> 1.18 s.
big_cyclic big cyclic tests 2.170 s. TIMEOUT ERROR running time:> 2.17 s.
single_letter_with_some_tweaks 2.170 s. TIMEOUT ERROR running time:> 2.17 s.
same_small_pattern_with_small_tweaks 2.160 s. TIMEOUT ERROR execution failed time:> 2.16 s.
same_big_pattern_with_small_tweaks 4.660 s. TIMEOUT ERROR execution failed time:> 4.66 s.
small_pattern_with_tweaks_in_one_place 4.700 s TIMEOUT ERROR execution failed time:> 4.70 s.
Any help or tips will be convenient!
public class test { public static void main(String[] args) { long startTime = System.nanoTime(); System.out.println("solution: " + solution("abababa")); long endTime = System.nanoTime(); long duration = endTime - startTime; System.out.println("duration: " + duration/1000000.0 + " seconds"); } public static int solution(String S) { int solution = 0, N = S.length(); String P; for (int K = 1; K <= N; K++) { P = S.substring(0, K); int T = calculateT(P, S); int tmpSolution = K * T; if (tmpSolution > solution) { solution = tmpSolution; } } return solution; } public static int calculateT(String P, String S) { int T = 0, indexOfStart = 0; while (indexOfStart > -1) { T++; indexOfStart = S.indexOf(P, indexOfStart+1); } return T; } }