# O(n) solution : still time limit exceeds?

• import java.util.;
import java.lang.
;
import java.io.*;

public class Solution {

``````    public List<String> findRepeatedDnaSequences(String s) {

HashMap<String, Integer> encodings = new HashMap<String, Integer>();
encodings.put("A", 1);
encodings.put("C", 2);
encodings.put("G", 3);
encodings.put("T", 4);

HashMap duplicates = new HashMap<Integer, String>();

List<String> solution = new ArrayList<String>();

if (s.length() < 10) return solution;

StringBuilder str = new StringBuilder(s.substring(0,10));

int initialHash = 0;
int power  = 10;

int last_firstEncoding = encodings.get(""+s.charAt(0));
for (int i = 0; i < 10; i++)
{
int encoding = 0;
if (encodings.get((""+s.charAt(i))) != null)
{
encoding = encodings.get(""+s.charAt(i));

}
initialHash += encoding*Math.pow(2, power);
power--;
}
duplicates.put(initialHash, s.substring(0, 10));

str = str.deleteCharAt(0);
for (int i = 10; i < s.length(); i++)
{
char currentChar = s.charAt(i);
initialHash -=last_firstEncoding*Math.pow(2, 10);
initialHash = 2*(initialHash + encodings.get((""+currentChar)));

str = str.append(currentChar);
if (duplicates.get(initialHash) != null)
{
}

else
{
duplicates.put(initialHash, str.toString());
}
last_firstEncoding = encodings.get((""+s.charAt(i-9)));
str = str.deleteCharAt(0);
}

return solution;
}
``````

}

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.