Loading…

easyStrings0Frequently asked

Repeated String

Q: How do you solve Repeated String using the Build the String, Then Count (Naive — Don't Ship) approach?

When to use it: Mention only to expose why it fails — it demonstrates you understand the constraint that kills it. The most direct reading of the problem is 'make the first `n` characters, then count the a's'. It is worth articulating *because* it is what most people picture first — and then immediately rejecting it. **Why it is tempting.** It maps one-to-one onto the words of the problem: the string is `s` repeated, so build `s` repeated, slice to `n`, count. The logic is trivially correct. **Why it is fatal here.** The constraint `n ≤ 10¹²` is not decoration — it is the adversary. A trillion characters is on the order of a terabyte of memory and a trillion character comparisons. The program will exhaust memory or time out long before it answers. This is the textbook case where a *correct* algorithm is still *wrong* for the input size. **The lesson it teaches.** Whenever a problem hands you an absurdly large bound, it is signalling that the intended solution does not touch every element. Here that nudge points straight at periodicity: the string repeats, so we should count once per period and scale arithmetically rather than enumerate. Time complexity: O(n). Space complexity: O(n).

Q: How do you solve Repeated String using the Integer Math — Full Repeats + Remainder Prefix (Optimal) approach?

When to use it: The intended answer. Phrase it as 'count per copy, multiply by whole copies, add the leftover prefix'. Because the string is `s` tiled infinitely, the first `n` characters have a rigid structure: a whole number of complete copies of `s` followed by one partial copy. Express that with one `divmod`: `fullCopies = n // L` and `remainder = n % L`, where `L = |s|`. **Why multiplication replaces a loop.** Every complete copy of `s` is character-for-character identical, so each contributes *exactly* the same number of 'a' — call it `countA = count of 'a' in s`. Instead of scanning `fullCopies` copies, we scan `s` once and multiply: `fullCopies * countA`. That single multiplication is where the trillion-scale `n` gets tamed — `n` only ever appears inside cheap integer division and a product, never as a loop bound. **Why the remainder prefix.** After the whole copies, the first `n` characters include the *leading* `remainder` characters of the next copy — that's `s[: remainder]`. We count 'a' in just those characters and add it. We deliberately count the prefix of `s`, not an arbitrary slice, because the infinite string always restarts `s` from index 0 after each copy. **Why `n < L` needs no special case.** If `n` is smaller than one copy, `fullCopies = n // L = 0`, so the first term vanishes and `remainder = n`, making the answer purely `count of 'a' in s[: n]`. The same expression handles small and huge `n` identically — no branching required. **Why `long` in Java.** With `s = "a"` and `n = 10¹²`, the result is `10¹²`, far beyond `int`'s ~2.1×10⁹ ceiling. Declare `n` and the running total as `long`, or the product overflows to a wrong (often negative) value. Python's arbitrary-precision ints make this free. Time complexity: O(|s|). Space complexity: O(1).

Arrays & Hashing · 14 of 83 · 7 min

There is a string s of lowercase English letters that is repeated infinitely many times. Given an integer n, find and print the number of letter 'a' in the first n characters of the infinitely repeating string.

For example, if s = "abcac" and n = 10, the first 10 characters are "abcacabcac", which contains 4 occurrences of 'a'.

In plain English

The infinite string is just s tiled over and over. The first n characters consist of some whole number of complete copies of s followed by a partial leading chunk of s. Count 'a' per copy, scale by the number of whole copies, and add the 'a' in the partial chunk. The trillion-scale n is the entire point — it rules out building the string.

Examples

Example 1

Input: s = "aba", n = 10
Output: 7
Note: L = 3, full copies = 10 // 3 = 3, remainder = 10 % 3 = 1. 'a' per copy = 2 → 3*2 = 6. Prefix s[:1] = "a" → 1 more. Total = 7.

Example 2

Input: s = "a", n = 1000000000000
Output: 1000000000000
Note: Every character is 'a'. full copies = 10¹², remainder = 0 → 10¹² * 1 + 0. Building the string is impossible; the math is instant.

Example 3

Input: s = "abcac", n = 10
Output: 4
Note: L = 5, full copies = 2, remainder = 0. 'a' per copy = 2 → 2*2 = 4, no prefix to add.

Constraints

1 ≤ |s| ≤ 100
1 ≤ n ≤ 10¹² (n can be far larger than |s|)
s consists of lowercase English letters only

Clarifying questions4First question: How large can n be?Explore questions

Q1.How large can n be?
Up to 10¹². That immediately rules out constructing the string — a trillion characters won't fit in memory and counting them would time out.
Q2.Can n be smaller than the length of s?
Yes. Then there are zero complete copies and the answer is just the 'a' count in the first n characters of s. The same formula handles it (n // L = 0).
Q3.Are we counting only the letter 'a'?
Yes, specifically lowercase 'a'. The approach generalises to any character, but the prompt fixes 'a'.
Q4.Could the answer overflow a 32-bit integer?
Yes in Java: up to 10¹² / 1 ≈ 10¹² 'a's. Use long for the result; Python ints are unbounded so it's automatic there.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Don't build the giant string — n can be up to 10¹². Count 'a' in one copy of s, multiply by the number of complete copies that fit (n // len(s)), then add the 'a' count in the leftover prefix s[: n % len(s)]. Answer = (n // L) * countA + count of 'a' in the first (n % L) characters.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you spot that n up to 10¹² forbids building the string, and instead decompose the count into full repeats (multiply) plus a remainder prefix (count once).

Where candidates slip

Constructing the repeated string (s * (n // len(s) + 1))[:n] and counting — correct logic but O(n) memory/time that times out and can crash for n = 10¹².

How to stand out

Derive the formula from divmod, call out the long-overflow risk in Java, and note the edge case where n < len(s) is handled automatically by the same expression.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Build the String, Then Count (Naive — Don't Ship)	`O(n)`	`O(n)`	Mention only to expose why it fails — it demonstrates you understand the constraint that kills it.	Read
2	Integer Math — Full Repeats + Remainder Prefix (Optimal)Optimal	`O(\|s\|)`	`O(1)`	The intended answer. Phrase it as 'count per copy, multiply by whole copies, add the leftover prefix'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.Explore the full tree

Decomposing the first n characters

How to read it:The first n characters = (n // L) whole copies of s + a prefix of length n % L.

Rendering diagram…

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Build the String, Then Count (Naive — Don't Ship)

TimeO(n)SpaceO(n)

Mention only to expose why it fails — it demonstrates you understand the constraint that kills it.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The literal interpretation: physically create the first n characters and count 'a'. What does n = 10¹² do to that plan?

2Hint 2Explore hint

Repeat s enough times to reach length n, slice to exactly n, then count 'a'.

3Hint 3Explore hint

Now estimate memory: 10¹² characters ≈ a terabyte. This approach cannot run — that realisation is the whole lesson.

A · Core idea

The most direct reading of the problem is 'make the first n characters, then count the a's'. It is worth articulating because it is what most people picture first — and then immediately rejecting it.

Why it is tempting. It maps one-to-one onto the words of the problem: the string is s repeated, so build s repeated, slice to n, count. The logic is trivially correct.

Why it is fatal here. The constraint n ≤ 10¹² is not decoration — it is the adversary. A trillion characters is on the order of a terabyte of memory and a trillion character comparisons. The program will exhaust memory or time out long before it answers. This is the textbook case where a correct algorithm is still wrong for the input size.

The lesson it teaches. Whenever a problem hands you an absurdly large bound, it is signalling that the intended solution does not touch every element. Here that nudge points straight at periodicity: the string repeats, so we should count once per period and scale arithmetically rather than enumerate.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "aba", n = 10

Repeat

tile "aba" until length ≥ 10

State"abaabaabaa..."

Final result7 (but infeasible for n = 10¹²)

C · Code with teaching comments

Reference implementation previewpublic long repeatedString(String s, long n) { StringBuilder sb = new StringBuilder(); while (sb.length() < n) { sb.append(s); }Explore the full code

solution.javaJava

Build the String, Then Count (Naive — Don't Ship) — reference

2 teaching notes

1
public long repeatedString(String s, long n) {
2
    StringBuilder sb = new StringBuilder();
3
    // Keep appending copies of s until we have at least n characters — already hopeless
4
    // when n is 10¹².
5
    while (sb.length() < n) {
6
        sb.append(s);
7
    }
8
    // Casting n to int also overflows for n > 2³¹ − 1 — a second reason this can't work
9
    // at scale.
10
    String prefix = sb.substring(0, (int) n);
11
    long count = 0;
12
    for (int i = 0; i < prefix.length(); i++) {
13
        if (prefix.charAt(i) == 'a') count++;
14
    }
15
    return count;
16
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.16 lines

D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proof

A huge input bound is a hint, not a detail. n = 10¹² is the problem telling you 'you may not build me' — read the constraints before you commit to an approach.

ComplexityO(n) time, O(n) space — Constructing and scanning n characters is O(n) time and O(n) space. For n = 10¹² that is ~1 TB of memory and a trillion operations — infeasible.

E · Edge cases and pitfalls4s = "a", n = 1000000000000 — Tries to allocate ~10¹² characters → MemoryError / OutOfMemoryError. Demonstrates why we need the math approach.Explore edge cases

Edge cases handled

s = "a", n = 1000000000000Tries to allocate ~10¹² characters → MemoryError / OutOfMemoryError. Demonstrates why we need the math approach.

Pitfalls

Believing 'correct logic' is enough — it must also fit the input bounds.
Casting a 10¹² value to int (Java) silently overflows.
Ignoring the constraints section before choosing an approach.

03.2

Approach 2 of 2 · Optimal

Integer Math — Full Repeats + Remainder Prefix (Optimal)

TimeO(|s|)SpaceO(1)

The intended answer. Phrase it as 'count per copy, multiply by whole copies, add the leftover prefix'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

You never need the whole string — only how many 'a' are in its first n characters. The string is periodic with period L = |s|. How many complete periods fit in n, and what's left over?

2Hint 2Explore hint

n splits as n = (n // L) complete copies of s, plus a leftover prefix of length n % L. Each complete copy has exactly the same number of 'a'.

3Hint 3Explore hint

Count 'a' once in s, multiply by n // L, then add the 'a' count in s[: n % L]. Done in O(|s|), no giant string.

A · Core idea

Because the string is s tiled infinitely, the first n characters have a rigid structure: a whole number of complete copies of s followed by one partial copy. Express that with one divmod: fullCopies = n // L and remainder = n % L, where L = |s|.

Why multiplication replaces a loop. Every complete copy of s is character-for-character identical, so each contributes exactly the same number of 'a' — call it countA = count of 'a' in s. Instead of scanning fullCopies copies, we scan s once and multiply: fullCopies * countA. That single multiplication is where the trillion-scale n gets tamed — n only ever appears inside cheap integer division and a product, never as a loop bound.

Why the remainder prefix. After the whole copies, the first n characters include the leading remainder characters of the next copy — that's s[: remainder]. We count 'a' in just those characters and add it. We deliberately count the prefix of s, not an arbitrary slice, because the infinite string always restarts s from index 0 after each copy.

Why `n < L` needs no special case. If n is smaller than one copy, fullCopies = n // L = 0, so the first term vanishes and remainder = n, making the answer purely count of 'a' in s[: n]. The same expression handles small and huge n identically — no branching required.

Why `long` in Java. With s = "a" and n = 10¹², the result is 10¹², far beyond int's ~2.1×10⁹ ceiling. Declare n and the running total as long, or the product overflows to a wrong (often negative) value. Python's arbitrary-precision ints make this free.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "aba", n = 10

Interactive diagram

Why no string is ever built

Per-copy count

Active call / nodeSupporting contextReturned stateNot active

n flows only through division and a product — never a loop over n characters.

Final result7

C · Code with teaching comments

solution.javaJava

Integer Math — Full Repeats + Remainder Prefix (Optimal) — optimal

4 teaching notes

1
public long repeatedString(String s, long n) {
2
    long countA = 0;
3
    for (int i = 0; i < s.length(); i++) {
4
        if (s.charAt(i) == 'a') countA++;
5
    }
6
    // Integer division gives the number of whole copies of s within the first n
7
    // characters.
8
    long fullCopies = n / s.length();
9
    // Each whole copy has identical 'a' count — multiply instead of looping. Must be
10
    // long to avoid overflow.
11
    long total = fullCopies * countA;
12
    // The leftover length after the whole copies — the size of the trailing partial
13
    // copy.
14
    long remainder = n % s.length();
15
    // Count 'a' only in the first `remainder` characters of s (the partial copy).
16
    for (int i = 0; i < remainder; i++) {
17
        if (s.charAt(i) == 'a') total++;
18
    }
19
    return total;
20
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.20 lines

D · Why it works and complexityO(|s|) timeO(1) spaceOpen the invariant and proofExplore the proof

The whole solution is one divmod: quotient → 'how many full periods' (multiply the per-period count), remainder → 'how much of the next period' (count its prefix). This quotient-plus-remainder decomposition is the universal way to answer 'how many X in the first n of something periodic' without ever expanding it.

ComplexityO(|s|) time, O(1) space — Counting 'a' in s is O(|s|); counting in the prefix is O(|s|) at most; the rest is constant-time arithmetic. Total O(|s|) time (≤ 100 ops) and O(1) extra space — completely independent of n.

E · Edge cases and pitfalls6s = "a", n = 1000000000000 — countA = 1, fullCopies = 10¹², remainder = 0 → 10¹² * 1 = 10¹². Needs long in Java; instant.Explore edge cases

Edge cases handled

s = "a", n = 1000000000000countA = 1, fullCopies = 10¹², remainder = 0 → 10¹² * 1 = 10¹². Needs long in Java; instant.
s = "abc", n = 2n < L: fullCopies = 0, remainder = 2 → prefix "ab" has 1 'a' → returns 1.
s = "bbb", n = 999999999999countA = 0 → total stays 0 regardless of n. No 'a' anywhere.

Pitfalls

Using int instead of long in Java — the product overflows for large n.
Counting 'a' in the full s for the remainder instead of only s[: remainder].
Adding a needless special case for n < L — the formula already handles it via n // L = 0.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic long repeatedString(String s, long n) { long countA = 0; for (int i = 0; i < s.length(); i++) { if (s.charAt(i) == 'a') countA++; }Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Materialising the giant string

n up to 10¹² means ~1 TB of characters. Even though counting is correct, the allocation crashes or times out. Use division/modulo math instead.

Explore the code comparison

Don't write this

return (s * (n // len(s) + 1))[:n].count('a')

Write this instead

full, rem = divmod(n, len(s))
return full * s.count('a') + s[:rem].count('a')

Integer overflow in Java

With s = "a", n = 10¹², the answer is 10¹², which overflows a 32-bit int to a wrong value. The total and n must be long.

Explore the code comparison

Don't write this

int total = (int) (fullCopies * countA);

Write this instead

long total = fullCopies * countA;

Wrong remainder slice

The trailing partial copy is the FIRST n % L characters of s, not the whole copy. Counting all of s double-counts.

Explore the code comparison

Don't write this

return full * s.count('a') + s.count('a')

Write this instead

return full * s.count('a') + s[:rem].count('a')

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Full-repeats × per-copy count + remainder prefix

Code pattern to memorize

L = len(s)
fullCopies = n // L
remainder  = n % L
total = fullCopies * count(s, 'a')
      + count(s[:remainder], 'a')

Rules to remember

1Never materialise the repeated string — n up to 10¹² means the string would have a trillion characters and blow memory/time.
2Split the first n characters into n // L whole copies plus one partial prefix of length n % L.
3Each whole copy contributes the same count of 'a' → multiply, don't loop.
4Use int math; in Java the product can exceed int range, so the total must be `long`.
5The remainder prefix is s[: n % L] — count 'a' only in those leading characters, not the whole copy.
6If n < L, then n // L = 0 and the answer is purely the prefix count — the formula still works.

Use this pattern when

A value is conceptually huge/infinite but periodic, so you can reason per-period
You'd otherwise construct an enormous structure just to count something
The query is 'how many X in the first n of a repeating pattern'
Counting within one period is cheap and the rest is multiplication

Choose another pattern when

The pattern is not periodic / each position is unique → no per-period shortcut
n is tiny and constant → just build it; the math is overkill
You must return the actual characters, not a count → can't avoid materialising what you output
The 'period' changes over time → it isn't a fixed repeat

Interview takeaway

When something repeats infinitely, count within one period and scale with division/modulo — never build the whole thing. This 'quotient × per-period + remainder' decomposition is the same trick behind clock arithmetic, cycle detection, and 'nth digit of a repeating sequence' problems.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternPeriodic decomposition with divmod. When a structure repeats, split a query over its first n elements into (n // period) whole periods plus a remainder prefix, counting once per period and scaling by multiplication. Never expand the full structure.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Count any character c in first n
Coming soon
Replace 'a' with a parameter c — the divmod decomposition is identical.
Sum of first n digits of a repeating decimal
Coming soon
Same quotient × per-period + remainder idea applied to a periodic digit sequence.
Smallest Integer Divisible by K
Coming soon
Reasoning about repeated/periodic structure with modular arithmetic instead of construction.
Lily's Homework / Cyclic patterns
Coming soon
Another HackerRank-style problem where periodicity replaces brute enumeration.

Same pattern

←

String to Integer (atoi)

Continue · Next problem

Ransom Note

easyStrings0Frequently asked

Repeated String

Arrays & Hashing · 14 of 83 · 7 min

For example, if s = "abcac" and n = 10, the first 10 characters are "abcacabcac", which contains 4 occurrences of 'a'.

In plain English

Examples

Example 1

Input: s = "aba", n = 10
Output: 7
Note: L = 3, full copies = 10 // 3 = 3, remainder = 10 % 3 = 1. 'a' per copy = 2 → 3*2 = 6. Prefix s[:1] = "a" → 1 more. Total = 7.

Example 2

Input: s = "a", n = 1000000000000
Output: 1000000000000
Note: Every character is 'a'. full copies = 10¹², remainder = 0 → 10¹² * 1 + 0. Building the string is impossible; the math is instant.

Example 3

Input: s = "abcac", n = 10
Output: 4
Note: L = 5, full copies = 2, remainder = 0. 'a' per copy = 2 → 2*2 = 4, no prefix to add.

Constraints

1 ≤ |s| ≤ 100
1 ≤ n ≤ 10¹² (n can be far larger than |s|)
s consists of lowercase English letters only

Clarifying questions4First question: How large can n be?Explore questions

Q1.How large can n be?
Up to 10¹². That immediately rules out constructing the string — a trillion characters won't fit in memory and counting them would time out.
Q2.Can n be smaller than the length of s?
Yes. Then there are zero complete copies and the answer is just the 'a' count in the first n characters of s. The same formula handles it (n // L = 0).
Q3.Are we counting only the letter 'a'?
Yes, specifically lowercase 'a'. The approach generalises to any character, but the prompt fixes 'a'.
Q4.Could the answer overflow a 32-bit integer?
Yes in Java: up to 10¹² / 1 ≈ 10¹² 'a's. Use long for the result; Python ints are unbounded so it's automatic there.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you spot that n up to 10¹² forbids building the string, and instead decompose the count into full repeats (multiply) plus a remainder prefix (count once).

Where candidates slip

Constructing the repeated string (s * (n // len(s) + 1))[:n] and counting — correct logic but O(n) memory/time that times out and can crash for n = 10¹².

How to stand out

Derive the formula from divmod, call out the long-overflow risk in Java, and note the edge case where n < len(s) is handled automatically by the same expression.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Build the String, Then Count (Naive — Don't Ship)	`O(n)`	`O(n)`	Mention only to expose why it fails — it demonstrates you understand the constraint that kills it.	Read
2	Integer Math — Full Repeats + Remainder Prefix (Optimal)Optimal	`O(\|s\|)`	`O(1)`	The intended answer. Phrase it as 'count per copy, multiply by whole copies, add the leftover prefix'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.Explore the full tree

Decomposing the first n characters

How to read it:The first n characters = (n // L) whole copies of s + a prefix of length n % L.

Rendering diagram…

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Build the String, Then Count (Naive — Don't Ship)

TimeO(n)SpaceO(n)

Mention only to expose why it fails — it demonstrates you understand the constraint that kills it.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The literal interpretation: physically create the first n characters and count 'a'. What does n = 10¹² do to that plan?

2Hint 2Explore hint

Repeat s enough times to reach length n, slice to exactly n, then count 'a'.

3Hint 3Explore hint

Now estimate memory: 10¹² characters ≈ a terabyte. This approach cannot run — that realisation is the whole lesson.

A · Core idea

Why it is tempting. It maps one-to-one onto the words of the problem: the string is s repeated, so build s repeated, slice to n, count. The logic is trivially correct.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "aba", n = 10

Repeat

tile "aba" until length ≥ 10

State"abaabaabaa..."

Final result7 (but infeasible for n = 10¹²)

C · Code with teaching comments

Reference implementation previewpublic long repeatedString(String s, long n) { StringBuilder sb = new StringBuilder(); while (sb.length() < n) { sb.append(s); }Explore the full code

solution.javaJava

Build the String, Then Count (Naive — Don't Ship) — reference

2 teaching notes

1
public long repeatedString(String s, long n) {
2
    StringBuilder sb = new StringBuilder();
3
    // Keep appending copies of s until we have at least n characters — already hopeless
4
    // when n is 10¹².
5
    while (sb.length() < n) {
6
        sb.append(s);
7
    }
8
    // Casting n to int also overflows for n > 2³¹ − 1 — a second reason this can't work
9
    // at scale.
10
    String prefix = sb.substring(0, (int) n);
11
    long count = 0;
12
    for (int i = 0; i < prefix.length(); i++) {
13
        if (prefix.charAt(i) == 'a') count++;
14
    }
15
    return count;
16
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.16 lines

D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proof

A huge input bound is a hint, not a detail. n = 10¹² is the problem telling you 'you may not build me' — read the constraints before you commit to an approach.

ComplexityO(n) time, O(n) space — Constructing and scanning n characters is O(n) time and O(n) space. For n = 10¹² that is ~1 TB of memory and a trillion operations — infeasible.

E · Edge cases and pitfalls4s = "a", n = 1000000000000 — Tries to allocate ~10¹² characters → MemoryError / OutOfMemoryError. Demonstrates why we need the math approach.Explore edge cases

Edge cases handled

s = "a", n = 1000000000000Tries to allocate ~10¹² characters → MemoryError / OutOfMemoryError. Demonstrates why we need the math approach.

Pitfalls

Believing 'correct logic' is enough — it must also fit the input bounds.
Casting a 10¹² value to int (Java) silently overflows.
Ignoring the constraints section before choosing an approach.

03.2

Approach 2 of 2 · Optimal

Integer Math — Full Repeats + Remainder Prefix (Optimal)

TimeO(|s|)SpaceO(1)

The intended answer. Phrase it as 'count per copy, multiply by whole copies, add the leftover prefix'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

You never need the whole string — only how many 'a' are in its first n characters. The string is periodic with period L = |s|. How many complete periods fit in n, and what's left over?

2Hint 2Explore hint

n splits as n = (n // L) complete copies of s, plus a leftover prefix of length n % L. Each complete copy has exactly the same number of 'a'.

3Hint 3Explore hint

Count 'a' once in s, multiply by n // L, then add the 'a' count in s[: n % L]. Done in O(|s|), no giant string.

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "aba", n = 10

Interactive diagram

Why no string is ever built

Per-copy count

Active call / nodeSupporting contextReturned stateNot active

n flows only through division and a product — never a loop over n characters.

Final result7

C · Code with teaching comments

solution.javaJava

Integer Math — Full Repeats + Remainder Prefix (Optimal) — optimal

4 teaching notes

1
public long repeatedString(String s, long n) {
2
    long countA = 0;
3
    for (int i = 0; i < s.length(); i++) {
4
        if (s.charAt(i) == 'a') countA++;
5
    }
6
    // Integer division gives the number of whole copies of s within the first n
7
    // characters.
8
    long fullCopies = n / s.length();
9
    // Each whole copy has identical 'a' count — multiply instead of looping. Must be
10
    // long to avoid overflow.
11
    long total = fullCopies * countA;
12
    // The leftover length after the whole copies — the size of the trailing partial
13
    // copy.
14
    long remainder = n % s.length();
15
    // Count 'a' only in the first `remainder` characters of s (the partial copy).
16
    for (int i = 0; i < remainder; i++) {
17
        if (s.charAt(i) == 'a') total++;
18
    }
19
    return total;
20
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.20 lines

D · Why it works and complexityO(|s|) timeO(1) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls6s = "a", n = 1000000000000 — countA = 1, fullCopies = 10¹², remainder = 0 → 10¹² * 1 = 10¹². Needs long in Java; instant.Explore edge cases

Edge cases handled

s = "a", n = 1000000000000countA = 1, fullCopies = 10¹², remainder = 0 → 10¹² * 1 = 10¹². Needs long in Java; instant.
s = "abc", n = 2n < L: fullCopies = 0, remainder = 2 → prefix "ab" has 1 'a' → returns 1.
s = "bbb", n = 999999999999countA = 0 → total stays 0 regardless of n. No 'a' anywhere.

Pitfalls

Using int instead of long in Java — the product overflows for large n.
Counting 'a' in the full s for the remainder instead of only s[: remainder].
Adding a needless special case for n < L — the formula already handles it via n // L = 0.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic long repeatedString(String s, long n) { long countA = 0; for (int i = 0; i < s.length(); i++) { if (s.charAt(i) == 'a') countA++; }Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Materialising the giant string

n up to 10¹² means ~1 TB of characters. Even though counting is correct, the allocation crashes or times out. Use division/modulo math instead.

Explore the code comparison

Don't write this

return (s * (n // len(s) + 1))[:n].count('a')

Write this instead

full, rem = divmod(n, len(s))
return full * s.count('a') + s[:rem].count('a')

Integer overflow in Java

With s = "a", n = 10¹², the answer is 10¹², which overflows a 32-bit int to a wrong value. The total and n must be long.

Explore the code comparison

Don't write this

int total = (int) (fullCopies * countA);

Write this instead

long total = fullCopies * countA;

Wrong remainder slice

The trailing partial copy is the FIRST n % L characters of s, not the whole copy. Counting all of s double-counts.

Explore the code comparison

Don't write this

return full * s.count('a') + s.count('a')

Write this instead

return full * s.count('a') + s[:rem].count('a')

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Full-repeats × per-copy count + remainder prefix

Code pattern to memorize

L = len(s)
fullCopies = n // L
remainder  = n % L
total = fullCopies * count(s, 'a')
      + count(s[:remainder], 'a')

Rules to remember

1Never materialise the repeated string — n up to 10¹² means the string would have a trillion characters and blow memory/time.
2Split the first n characters into n // L whole copies plus one partial prefix of length n % L.
3Each whole copy contributes the same count of 'a' → multiply, don't loop.
4Use int math; in Java the product can exceed int range, so the total must be `long`.
5The remainder prefix is s[: n % L] — count 'a' only in those leading characters, not the whole copy.
6If n < L, then n // L = 0 and the answer is purely the prefix count — the formula still works.

Use this pattern when

A value is conceptually huge/infinite but periodic, so you can reason per-period
You'd otherwise construct an enormous structure just to count something
The query is 'how many X in the first n of a repeating pattern'
Counting within one period is cheap and the rest is multiplication

Choose another pattern when

The pattern is not periodic / each position is unique → no per-period shortcut
n is tiny and constant → just build it; the math is overkill
You must return the actual characters, not a count → can't avoid materialising what you output
The 'period' changes over time → it isn't a fixed repeat

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Count any character c in first n
Coming soon
Replace 'a' with a parameter c — the divmod decomposition is identical.
Sum of first n digits of a repeating decimal
Coming soon
Same quotient × per-period + remainder idea applied to a periodic digit sequence.
Smallest Integer Divisible by K
Coming soon
Reasoning about repeated/periodic structure with modular arithmetic instead of construction.
Lily's Homework / Cyclic patterns
Coming soon
Another HackerRank-style problem where periodicity replaces brute enumeration.

Same pattern

←

String to Integer (atoi)

Continue · Next problem

Ransom Note