Facebook Interview Question
Software EngineersCountry: United States
Interview Type: In-Person
boolean isPeriod(String s) {
StringBuilder str = new StringBuilder(s s);
str.deleteCharAt(0);
str.deleteCharAt(str.length() - 1);
return strStr(str.toString(), s); //KMP strStr(T, S) to find if T has S in it.
}
//Solution to follow-up
//This method looks for the repeating pattern in string
private static String getPeriod(String string) { // O(n * n)
//for every possible period size i, check if it's valid
for (int i = 1; i <= string.length() / 2; i ) {
if (string.length() % i == 0) {
String period = string.substring(0, i);
int j = i;
while(j + i <= string.length()) {
if (period.equals(string.substring(j, j i))) {
j = j + i;
if(j == string.length()) { //period valid through entire string
return period;
}
} else {
break;
}
}
}
}
return null; //string is not periodic
}
Looking for interview experience sharing and mentors?
Visit A++ Coding Bootcamp at aonecode.com.
Taught by experienced engineers/interviewers from FB, Google and Uber,
our ONE TO ONE courses cover everything in an interview including
latest interview questions sorted by companies,
SYSTEM DESIGN Courses (highly recommended for people interviewing with FLAG)
ALGORITHMS (conquer DP, Graph, Greed and other advanced algo problems),
and mock interviews.
Our students got offers from Google, Uber, Facebook, Amazon and other top companies after a few weeks of training.
Welcome to email us with any questions. Thanks for reading.
def factors(n):
f=[]
for i in range(1,n):
if n%i==0:
f.append(i)
return f
def periodic(s):
f=factors(len(s))
for i in f:
m=len(s)/i
#return s[:i]*3
if s[:i]*int(m)==s:
return True
return False
print(periodic('abcabc'))
def factors(n):
f=[]
for i in range(1,n):
if n%i==0:
f.append(i)
return f
def periodic(s):
f=factors(len(s))
for i in f:
m=len(s)/i
#return s[:i]*3
if s[:i]*int(m)==s:
return True
return False
def periodic (my_str = "aaaaabbbbb"):
str_len = len(my_str)
period_sizes = []
reaps = []
for i in range(1, int(str_len/2)+1):
if str_len%i == 0:
period_sizes.append(i)
for period_size in period_sizes:
reaps.append(my_str.count(my_str[:period_size]))
for i in range (0,len(period_sizes)):
if period_sizes[i] * reaps [i] == str_len:
return True
return (False)
a slightly improved version
#!/usr/bin/env python3
"""
Find whether string S is periodic. Periodic indicates S = nP. e.g.
if S = abcabc, then n = 3, and P = abc
if S = xxxx, n = 1, and P = x
follow up, given string S, find out repetitive pattern of P
"""
def factors(n):
f = []
for i in range(1, n):
if n % i == 0:
f.append(i)
return f
def periodic(s):
f = factors(len(s))
for i in f:
m = len(s)/i
if s[:i] * int(m) == s:
print(i, s[:i], s)
return True
return False
# driver
if __name__ == "__main__":
assert True == periodic('abcabc')
assert False == periodic('abcabcd')
pattern = []
string = "sarojasaroja"
if len(set(string)) ==1:
print(string[0])
else:
for outer in range(2,int(len(string)/2)+1):
listt = []
if len(string)%outer == 0:
for inner in range(outer):
for innermost in range(inner,int(len(string)/outer)):
if(string[innermost+inner] != string[innermost + outer]):
break
else :
listt.append(string[inner])
if len(listt) == int(len(string)/outer) :
pattern.append(string[inner])
if len(pattern) == outer :
break
print (pattern)
pattern = []
string = "sarojasaroja"
if len(set(string)) ==1:
print(string[0])
else:
for outer in range(2,int(len(string)/2)+1):
listt = []
if len(string)%outer == 0:
for inner in range(outer):
for innermost in range(inner,int(len(string)/outer)):
if(string[innermost+inner] != string[innermost + outer]):
break
else :
listt.append(string[inner])
if len(listt) == int(len(string)/outer) :
pattern.append(string[inner])
if len(pattern) == outer :
break
print (pattern)
pattern = []
string = "sarojasaroja"
if len(set(string)) ==1:
print(string[0])
else:
for outer in range(2,int(len(string)/2)+1):
listt = []
if len(string)%outer == 0:
for inner in range(outer):
for innermost in range(inner,int(len(string)/outer)):
if(string[innermost+inner] != string[innermost + outer]):
break
else :
listt.append(string[inner])
if len(listt) == int(len(string)/outer) :
pattern.append(string[inner])
if len(pattern) == outer :
break
print (pattern)
pattern = []
string = "sarojasaroja"
if len(set(string)) ==1:
print(string[0])
else:
for outer in range(2,int(len(string)/2)+1):
listt = []
if len(string)%outer == 0:
for inner in range(outer):
for innermost in range(inner,int(len(string)/outer)):
if(string[innermost+inner] != string[innermost + outer]):
break
else :
listt.append(string[inner])
if len(listt) == int(len(string)/outer) :
pattern.append(string[inner])
if len(pattern) == outer :
break
print (pattern)
def isPeriodic(input, start, end=1):
if end-start > len(input) - end:
return False
did_match = True
for x in range(start, end):
#print (" check " + str(x) + " " + str(start) + " " + str(end) + " => " + str(len(input)))
if input[x] != input[end - start + x]:
did_match = False
break
if did_match:
delta = end - start
start2 = end
if end + delta == len(input):
return True
did_match = isPeriodic(input, end, end + delta)
if not did_match:
return isPeriodic(input, start, end+1)
return did_match
if __name__ == "__main__":
S = "ababab"
print(S + " => " + str(isPeriodic(S, 0)))
S = "xxxxxx"
print(S + " => " + str(isPeriodic(S, 0)))
S = "aabbaaabba"
print(S + " => " + str(isPeriodic(S, 0)))
S = "aabbaabbaabb"
print(S + " => " + str(isPeriodic(S, 0)))
S = "abcd"
print(S + " => " + str(isPeriodic(S, 0)))
S = "abbaabbaabba"
print(S + " => " + str(isPeriodic(S,
static boolean isPeriodic(String s) {
for(int i=s.length(); i>1; i--) {
int length = s.length();
String p = s.substring(0, length / i);
if (isSubstring(s, p)) {
System.out.println(p);
return true;
}
}
return false;
}
static boolean isSubstring(String s, String p) {
for (int i=0; i<s.length(); i+=p.length()) {
if (!s.substring(i, i+p.length()).equals(p)) return false;
}
return true;
}
static boolean isPeriodic(String s) {
for(int i=s.length(); i>1; i--) {
int length = s.length();
String p = s.substring(0, length / i);
if (isSubstring(s, p)) {
System.out.println(p);
return true;
}
}
return false;
}
static boolean isSubstring(String s, String p) {
for (int i=0; i<s.length(); i+=p.length()) {
if (!s.substring(i, i+p.length()).equals(p)) return false;
}
return true;
}
import java.util.Optional;
class Main {
public static void main(String[] args) {
System.out.print("String: " + args[0]);
Optional<String> patOp = findPattern(args[0]);
if (patOp.isPresent()) {
System.out.println(" Pattern: " + patOp.get());
} else {
System.out.println(" No pattern found.");
}
}
// The algorithm is to concatenate the string to itself, take the result without
// the first and the last characters and look for the string inside this result.
// If present - the string is periodic.
// To find the pattern, take the index of the string in the result, cut the result
// up until this index and add the first character of the original string in
// the beginning.
// Example:
// original: aabbaaabba
// result to look in: [a]abbaaabbaaabbaaabb[a]
// found the original at index 4: 0123|--------|
// prefix: abba, add back the first character -> aabba
public static Optional<String> findPattern(String str) {
String test = str + str;
String sub = test.substring(1, test.length() - 1);
int index = sub.indexOf(str);
if (index < 0) {
return Optional.empty();
}
return Optional.of(str.charAt(0) + sub.substring(0, index));
}
}
const isPeriodic = (str) => {
let currStr = str.charAt(0);
let n = 1;
let i = 1;
while (i < str.length) {
if (currStr.charAt(0) === str.charAt(i)) {
if (currStr === str.substring(i, i + currStr.length)) {
n++;
} else {
currStr += str.substring(i, i + currStr.length);
}
i += currStr.length - 1;
} else {
let newStr = "";
while (n >= 1) {
newStr += currStr;
n--;
}
n = 1;
newStr += str.charAt(i);
currStr = newStr;
}
i++;
}
console.log(`n: ${n}, p: ${currStr}`);
};
const isPeriodic = (str) => {
let currStr = str.charAt(0);
let n = 1;
let i = 1;
while (i < str.length) {
if (currStr.charAt(0) === str.charAt(i)) {
if (currStr === str.substring(i, i + currStr.length)) {
n++;
} else {
currStr += str.substring(i, i + currStr.length);
}
i += currStr.length - 1;
} else {
let newStr = "";
while (n >= 1) {
newStr += currStr;
n--;
}
n = 1;
newStr += str.charAt(i);
currStr = newStr;
}
i++;
}
console.log(`n: ${n}, p: ${currStr}`);
};
public class PeriodicStringTest {
public static void main(String[] args) {
findRepetitivePattern("aabbaaabba");
findRepetitivePattern("xxxxxxxxxx");
findRepetitivePattern("ababab");
findRepetitivePattern("aa");
findRepetitivePattern("aaabaa");
}
public static void findRepetitivePattern(String str) {
if (str.length() <= 1) {
System.out.println("String '" + str + "' is not periodic.");
return;
}
String repititivePattern = null;
boolean periodic = false;
for (int i = 0; i < str.length() - 1; i++) {
repititivePattern = str.substring(0, i+1);
String splits[] = str.split(repititivePattern, -1);
for (String split : splits) {
if (split.equals("")) {
periodic = true;
} else {
periodic = false;
break;
}
}
if (periodic) {
System.out.println("String '" + str + "' ===> P = " + repititivePattern + ", n = " + (splits.length-1));
return;
}
}
System.out.println("String '" + str + "' is not periodic.");
}
}
Output:
String 'aabbaaabba' ===> P = aabba, n = 2
String 'xxxxxxxxxx' ===> P = x, n = 10
String 'ababab' ===> P = ab, n = 3
String 'aa' ===> P = a, n = 2
String 'aaabaa' is not periodic.
public class PeriodicStringTest {
public static void main(String[] args) {
findRepetitivePattern("aabbaaabba");
findRepetitivePattern("xxxxxxxxxx");
findRepetitivePattern("ababab");
findRepetitivePattern("aa");
findRepetitivePattern("aaabaa");
}
public static void findRepetitivePattern(String str) {
if (str.length() <= 1) {
System.out.println("String '" + str + "' is not periodic.");
return;
}
String repititivePattern = null;
boolean periodic = false;
for (int i = 0; i < str.length() - 1; i++) {
repititivePattern = str.substring(0, i+1);
String splits[] = str.split(repititivePattern, -1);
for (String split : splits) {
if (split.equals("")) {
periodic = true;
} else {
periodic = false;
break;
}
}
if (periodic) {
System.out.println("String '" + str + "' ===> P = " + repititivePattern + ", n = " + (splits.length-1));
return;
}
}
System.out.println("String '" + str + "' is not periodic.");
}
}
/*
* T: O(n^2)
* S: O(n)
* */
public class PeriodicPattern{
static boolean ans = false;
public static void main(String[] args){
String str = "aabbaaabba";
for(int i=0; i<str.length()/2+1; i++){
String s = str.substring(0, i+1);
dfs(str, s.length(), s);
}
System.out.println(ans);
}
public static void dfs(String str, int start, String p){
if(start == str.length()){
ans = true;
System.out.println(p);
return;
}
if(str.indexOf(p, start) == start)
dfs(str, start+p.length(), p);
}
}
def periodic (my_str):
str_len = len(my_str)
period_sizes = []
reaps = []
for i in range(1, int(str_len/2)+1):
if str_len%i == 0:
period_sizes.append(i)
for period_size in period_sizes:
reaps.append(my_str.count(my_str[:period_size]))
for i in range (0,len(period_sizes)):
if period_sizes[i] * reaps [i] == str_len:
return True
return (False)
public static string FindPeriodicPattern(string s)
{
StringBuilder currPatt = new StringBuilder();
int n = 1, i = 0, innerI = 0;
bool isCurrMatch = false;
while (i < s.Length)
{
innerI = i;
foreach (var ch in currPatt.ToString())
{
if (s[innerI] == ch)
{
isCurrMatch = true;
innerI++;
continue;
}
else
{
isCurrMatch = false;
currPatt.Append(s[i]);
break;
}
}
if (isCurrMatch)
{
i = innerI;
n++;
}
else
{
if(string.IsNullOrEmpty(currPatt.ToString()))
currPatt.Append(s[i]);
i++;
}
}
return n > 1 ? currPatt.ToString() : null;
}
// S = "ababab", then n=3, P= "ab"
// S = "xxxxxx", then n = 1, and P = "x"
// S = "aabbaaabba", then n = 2, and P = "aabba"
function findPattern(str) {
var pattern = '';
var n = 1;
for (var i = 0; i < str.length;) {
var step = pattern.length > 0 ? pattern.length : 1;
var test = str.substr(i, step);
if (test == pattern) {
// Possible a pattern
i += step;
n += 1;
} else {
i += 1;
pattern = str.substr(0, i);
n = 1;
}
}
return {n, pattern};
}
console.log("ababab => " + JSON.stringify(findPattern("ababab")))
console.log("xxxxxx => " + JSON.stringify(findPattern("xxxxxx")))
console.log("aabbaaabba => " + JSON.stringify(findPattern("aabbaaabba")))
static void Main( string [] args )
{
string s = "ababab";
int Period = 0;
string szRepeatString = "";
int l = s.Length;
for ( int subLen = 1 ; subLen <= l / 2 ; subLen++ )
{
if ( l % subLen != 0 ) continue;
string szStub = s.Substring( 0, subLen );
int nCopies = l / subLen;
int n;
for ( n = 1 ; n < nCopies ; n++ )
{
if( s.Substring( n * subLen, subLen ) != szStub )
{
break;
}
}
if ( n == nCopies )
{
szRepeatString = szStub;
Period = subLen;
break;
}
}
Console.WriteLine( "string = " + s + ", period = " + Period + ", sub string = " + szRepeatString );
}
{{def periodic_scan(S):
s = S
cnt = 1
i = 1
comp = s[:i]
s = s[i:]
while len(s) > 0:
if i > len(S)//2:
return "None"
elif comp == s[:i]:
s = s[i:]
cnt += 1
else:
i += 1
s = S
cnt = 1
comp = s[:i]
s = s[i:]
return comp,cnt
# implement
print(periodic_scan("ababab"))
print(periodic_scan("xxxxxx"))
print(periodic_scan("aabbaaabba"))
print(periodic_scan("abcdefg"))
print(periodic_scan("abcdefghijklmnopabcdefghijklmnopabcdefghijklmnop"))}}
def periodic_scan(S):
s = S
cnt = 1
i = 1
comp = s[:i]
s = s[i:]
while len(s) > 0:
if i > len(S)//2:
return "None"
elif comp == s[:i]:
s = s[i:]
cnt += 1
else:
i += 1
s = S
cnt = 1
comp = s[:i]
s = s[i:]
return comp,cnt
# implement
print(periodic_scan("ababab"))
print(periodic_scan("xxxxxx"))
print(periodic_scan("aabbaaabba"))
print(periodic_scan("abcdefg"))
print(periodic_scan("abcdefghijklmnopabcdefghijklmnopabcdefghijklmnop"))
A more pythonic solution:
def smallest_period(s):
n = len(s)
i = 0
while i < n/2:
i += 1
if n % i == 0 :
p = s[:i]
comp = [ s[next:next+i] == p for next in range(i,n,i)]
if all(comp):
return (p,n//i)
return (s,1)
s = 'ababab'
exp = ('ab',3)
actual = smallest_period(s)
assert actual == exp, actual
s = 'xxxxxx'
exp = ('x',6)
actual = smallest_period(s)
assert actual == exp, actual
s = 'aabbaaabba'
exp = ('aabba',2)
actual = smallest_period(s)
assert actual == exp, actual
s = 'abcdefa'
exp = ('abcdefa',1)
actual = smallest_period(s)
assert actual == exp, actual
C++ program
#include <iostream>
#include <set>
#include <iterator>
// Some properties
// 1. Pattern should contain atleast one distinct character that is present in the string.
// 2. Size of the string should be multiple of the pattern size.
//
// Steps:
// A. Find the substring to start with that satisfies #1.
// B. See if that satisfies #2.
// C. If so check if that is a correct pattern.
// D. If B or C failed, traverse the string for the next pattern that satisfies A to C.
bool IsValidPattern(std::string s, std::string pattern)
{
// Property 2.
if (s.length() % pattern.length() == 0)
{
bool fValid = true;
for (int i = 0; i < s.length(); i+=pattern.length())
{
if (s.compare(i, pattern.length(), pattern) != 0)
{
fValid = false;
break;
}
}
if (fValid) return true;
}
return false;
}
void CheckPeriodic(std::string s, int nExepected, std::string expectedPattern)
{
// Unique letters
std::set<char> letters(s.begin(), s.end());
std::string::iterator it = s.begin();
int iIndex = 0;
// Property 1.
while ( iIndex <= s.length() / 2)
{
letters.erase(s[iIndex++]);
if (letters.size() == 0) break;
};
while (iIndex <= s.length() / 2)
{
std::string pattern = s.substr(0, iIndex);
if (IsValidPattern(s, pattern))
{
std::cout << s << " -> " << s.length() / pattern.length() << pattern;
if (nExepected == s.length() / pattern.length() && pattern == expectedPattern)
{
std::cout << " -> PASS" << std::endl;
}
else
{
std::cout << " -> failed, expected " << nExepected << expectedPattern << std::endl;
}
return;
}
iIndex++;
};
if (nExepected == 0)
{
std::cout << s << " -> PASS -> not periodic" << std::endl;
}
else
{
std::cout << s << " -> FAIL, expected " << nExepected << expectedPattern << std::endl;
}
}
int main()
{
CheckPeriodic("ababab", 3, "ab");
CheckPeriodic("abababababab", 6, "ab");
CheckPeriodic("xxxxxx", 6, "x");
CheckPeriodic("abcdafabcdafabcdaf", 3, "abcdaf");
CheckPeriodic("aabbaaabba", 2, "aabba");
CheckPeriodic("abcdeabcde", 2, "abcde");
CheckPeriodic("abc", 0, "");
CheckPeriodic("", 0, "");
return 0;
}
Output:
ababab -> 3ab -> PASS
abababababab -> 6ab -> PASS
xxxxxx -> 6x -> PASS
abcdafabcdafabcdaf -> 3abcdaf -> PASS
aabbaaabba -> 2aabba -> PASS
abcdeabcde -> 2abcde -> PASS
abc -> PASS -> not periodic
-> PASS -> not periodic
function isPeriodic(str) {
f: for (let i = 0; i <= str.length / 2; i += 1) {
window.P = str.substring(0, i);
if (!window.P) {
continue;
}
for (let x = 0; x < str.length; x += window.P.length) {
const currentPattern = str.substr(x, window.P.length);
if (currentPattern !== window.P) {
break;
} else if (x + window.P.length === str.length) {
console.log('RESULT', window.P, str.length / window.P.length);
break f;
}
}
}
}
Best Case is n;
Worst Case is n power 2
function getrepetitionPattern($str){
$arr = str_split($str);
$len = count($arr);
$pattern[0] = $arr[0];
$i = 0; //pattern index
$r = 1; //array init index
$j = 1; //array pointer
$n = 1;
while($j < $len){
if($arr[$j] == $pattern[$i]){
$j++; $i++;
if(count($pattern) == $i ) {
$i = 0;
$n++; //increase patter count
}
}else{
$pattern[] = $arr[$r];
$r ++; $j = $r;
$i = 0;
$n = 1;
}
}
print $n."".implode("",$pattern)."<br/><br/>";
}
$str1 = "abababab";
$str2 = "xxxxxxxk";
$str3 = "aabbaaabbaa";
getrepetitionPattern($str1);
echo '<br/>';
getrepetitionPattern($str2);
echo '<br/>';
getrepetitionPattern($str3);
def verify_p(s, p):
if len(s)%len(p) != 0:
return False
for i in range(len(p), len(s)):
mod = i%len(p)
if s[i] != p[mod]:
return False
return True
def find_p(s):
p = ''
k = 0
while k < len(s)-1:
p += s[k]
k += 1
ret = verify_p(s, p)
if ret:
print('found P:', s, p)
return
if __name__ == '__main__':
find_p('ababab')
find_p('abaabaabaaba')
private boolean checkIfPeriodic(String str) {
int dist = 1, prev = 0, next = 1;
boolean lastMatch = false;
while (next + dist <= str.length()) {
if (str.substring(prev, dist + prev).equals(str.substring(next, next + dist))) {
//Match found
prev = next;
next = next + dist;
lastMatch = true;
} else {
//Not matched
if(lastMatch){
prev=0;
}
dist++;
next = dist + prev;
lastMatch = false;
}
}
return lastMatch;
}
const isPeriodic = function(str, substr = null) {
const toMatch = substr ? substr : str.charAt(0)
const matchRx = new RegExp(toMatch, 'gi')
const match = str.match(matchRx)
if (match.length * toMatch.length === str.length) {
return { P: match[0], n: match.length }
}
return isPeriodic(str, str.slice(0, toMatch.length + 1))
}
const isPeriodic = function(str, substr = null) {
const toMatch = substr ? substr : str.charAt(0)
const matchRx = new RegExp(toMatch, 'gi')
const match = str.match(matchRx)
if (match.length * toMatch.length === str.length) {
return { P: match[0], n: match.length }
}
return isPeriodic(str, str.slice(0, toMatch.length + 1))
}
javascript implementation
function findPattenForS(S) {
let output = {
S: S,
n: 0,
P: ''
}
let tempPatten = S[0];
let tempMeetPatten = true, meetPatten = false;
let steps = 1;
for (steps = 1; steps<=S.length; steps++) {
tempPatten = S.substr(0, steps);
for (let i=0; i<S.length; i = i+steps) {
if (tempPatten !== S.substr(i, steps)) {
tempMeetPatten = false;
break;
}
}
if(tempMeetPatten) {
meetPatten = true;
break;
}
tempMeetPatten = true;
}
if (meetPatten) {
output.n = steps;
output.P = tempPatten;
}
return output;
}
console.log(findPattenForS("abababab"));
console.log(findPattenForS("xxxxxxxxx"));
console.log(findPattenForS("abcabcabc"));
console.log(findPattenForS("abababac"));
output:
{ S: 'abababab', n: 2, P: 'ab' }
{ S: 'xxxxxxxxx', n: 1, P: 'x' }
{ S: 'abcabcabc', n: 3, P: 'abc' }
{ S: 'abababac', n: 8, P: 'abababac' }
def isPeriodic(str1):
# is string is periodic n has to be 2, 3......n/2 at max
# brute force
n = int(len(str1)/2)
for i in range(1, n+1):
# i simply means the pattern length
#print(i)
temp = str1[0:i]
#print(i,temp)
found = None
for j in range(i,len(str1), i):
temp1 = str1[j:j+i]
#print(i, j,temp,temp1)
if temp == temp1:
continue
else:
found = False
break
if found is None:
return i, True
#print(temp1)
return -1,False
private static void CountSubstring(string s)
{
string substring = "";
bool isLoop = true;
int numberOfSubstrings = 0;
for (int i = 1; i < s.Length/2+1; i++)
{
isLoop = true;
substring = s.Substring(0, i);
if(s.Length%substring.Length == 0)
{
numberOfSubstrings = s.Length / substring.Length;
for (int j = 0; j < numberOfSubstrings; j++)
{
if(!s.Substring(j* substring.Length, substring.Length).Equals(substring))
{
isLoop = false;
break;
}
}
}
else
{
isLoop = false;
}
if (isLoop)
{
Console.WriteLine(string.Format("n={0},P={1}", numberOfSubstrings, substring));
return;
}
}
Console.WriteLine("Not a loop");
}
public class Periodic {
public static boolean isPeriodic(String s, int repeat){
int charsNo = s.length()/repeat;
String p = null;
for(int i=0;i<s.length();){
int j = i+charsNo-1;
String st = s.substring(i,j);
if(p==null)p = st;
else{
if(!p.equals(st)){
return false;
}
}
i = j+1;
}
return true;
}
public static void main(String[] args) {
String s = "ababab";
int n = 3;
System.out.println(isPeriodic(s,n));
s = "aabbaaabba";
n = 2;
System.out.println(isPeriodic(s,n));
s = "xxxxxxxx";
n = 8;
System.out.println(isPeriodic(s,n));
}
}
In Python:
def isPeriodic(s):
p=[]
for i in range(len(s)-1):
newss = s[:i+1]
p.append(newss)
new_p = []
print(p)
for ss in p:
if mayBePeriod(ss, newss):
new_p.append(ss)
p = new_p
for ss in p:
if isPeriod(ss, s):
print(ss)
return True
return False
def mayBePeriod(substr, word_t):
while True:
if word_t.startswith(substr):
word_t = word_t.partition(substr)[2]
else:
break
if word_t == "" or substr.startswith(word_t):
return True
else:
return False
def isPeriod(substr, word_t):
repeated = 0
while True:
if word_t.startswith(substr):
word_t = word_t.partition(substr)[2]
repeated += 1
else:
break
if repeated > 1 and word_t == "":
return True
return False
function isStrPeriodic(str) {
const strArr = Array.from(str);
let i = 0;
let pattern = '';
let count = 0;
while (i < strArr.length) {
if (i === 0 && pattern === '') {
pattern = strArr[i];
console.log('before continue')
i++;
continue;
}
const patternLength = pattern.length;
const wordArr = strArr.slice(i + 1, i + patternLength);
const wordStr = wordArr.join('');
const foundPatternArr = [];
const remainingLetters = strArr.slice(i);
for (let j = 0; j < remainingLetters.length; j += patternLength) {
foundPatternArr.push(remainingLetters.slice(j, j + patternLength).join(''))
}
const nonPatternFound = foundPatternArr.find(e => e !== pattern);
if (nonPatternFound) {
pattern += strArr[i];
i++;
continue;
}
// PATTERN FOUND
count = foundPatternArr.length + 1;
break;
i++;
}
return { pattern, count }
}
const { pattern, count } = isStrPeriodic('aabbaaabbaaabbax')
console.log('pattern:', pattern)
console.log('count:', count)
What am I missing about example number 2 in the question:
- Imposter June 07, 2019S = "xxxxxx", n = 1, then P = "x"
This doesn't seem consistent with the other examples.
In the first example, if n=3 and P=ab, then 3ab => ababab, that makes sense.
In the third example, if n = 2 and P=aabba, then 2aabba => aabbaaabba, that make sense.
But for exmple 2, if n=1 and P=x, then 1x should be x, not xxxxxx. I feel that in this case, if the P is x, then n should be 6, because 6x => xxxxxx
What am I missing? Am I fundamentally misunderstanding the problem here?