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);
    }
}
Tags:

Add a Comment

Your email address will not be published. Required fields are marked *