Counting occurences of a Letter in an infinite String

Question

I have the following String called s="abcac" that is repeated infinitely many times. This means that s will look like: s="abcacabcacabcacabcacabcac...." and n represents the substring of s.

For example, if s="monday" and n="10", the substring that we consider will be finalString="mondaymond", since the infinite string will be "mondaymondaymondaymonday..." and the first 10 characters of s are "mondaymond"

I am trying to count the occurrences of the letter "a" in finalString. This code is working properly, however when n>1000000 the program won't work.

In addition, if I change n from int to long, the for loop won't work in this case.

What would be the solution to this problem?

public static void main(String[] args){

            String s="abcac";
            int aCount=0;
            int n=1000;
            int j=0;


            char[] sCharArray=s.toCharArray();

            char[] finalString = new char[n];

            for(int i=0;i<n;i++){

                if(j==s.length())
                    j=0;

                finalString[i]=sCharArray[j];
                j++;


            }


            for(int i=0; i<n;i++){
                if(finalString[i]=='a')
                    aCount++;
            }


    System.out.println(aCount);

            }

Answer 1

I suggest finding how many times the base string is repeated, and the computing the occurrences of the letter using this information, plus the number of occurrences of the extra substring at the very end. For example:

String s = "monday";
int n = 10;
String chr = "a";

int baseNum = s.length() - s.replace(chr, "").length();
int baseCnt = (n / s.length()) * baseNum;
int index = n % s.length();
String left = s.substring(0, index);
int finalCnt = left.length() - left.replace(chr, "").length();
int totalCnt = baseCnt + finalCnt;

System.out.println("There were " + totalCnt + " letter " + chr + ".");

The basic idea here is efficiency. We don't actually need to create and work with a string of arbitrary length, because we know that it just repeats the same substring. Instead, we can just count occurrences in the substring, and project the total number by how many times that substring repeats.