Letter count in an infinite string
Problem:
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 letters a
‘s in the first n
letters of the infinite string.
Example:
s = 'abcac' n = 10
The substring we consider is abcacabcac
, the first 10 characters of the infinite string. There are 4 occurences of a
in the substring.
Function Description:
Write a function which takes the following parameter(s) and returns the frequency of a
in the substring.
s: a string to repeat n: the number of characters to consider
Constraints
1 <= s <=100 1 <= n <=10^12
Sample Input 1 :
aba 10
Sample Output 1:
7
Explanation:
The first n
letters of the infinite sub string is abaabaabaa
, in which there are 7
a
.
Sample Input 2:
a 100000000000
Sample Output 2:
100000000000
The first 100000000000
letters of the infinite sub string will have all as a
, So the answer is 100000000000
.
Solution:
import java.io.IOException; public class RepeatedString { static long repeatedString(String s, long n) { long noOfOccurence = 0; for (int i = 0; i < s.length(); i++) { if (s.charAt(i) == 'a') noOfOccurence++; } long repeat = n / s.length(); noOfOccurence *= repeat; for (int i = 0; i < n % s.length(); i++) { if (s.charAt(i) == 'a') noOfOccurence++; } return noOfOccurence; } public static void main(String[] args) throws IOException { String s = "aba"; long n = 10; long result = repeatedString(s, n); System.out.println(result); } }