Repeated String — HackerRank C++ Implementation
Problem:
Lilah has a string, s, of lowercase English letters that she repeated infinitely many times.
Given an integer, n, find and print the number of letter a's in the first n letters of Lilah's infinite string.
For example, if the string s = 'abcac' and n = 10, the substring we consider is , abcacabcac the first 10 characters of her infinite string. There are 4 occurrences of a in the substring.
Read the full problem here: Repeated String
Solution:
Let us consider that sub_str is the input string and str_len is the length of the infinite string we are considering.
When the str_len is less than the length of sub_str, we can easily calculate the number of a 's by iterating over the string.
Now, when the str_len is greater than the length of the sub_str length.
First, we will find the number of sub strings ( sub_str) in the string we are considering.
In many cases, the size of combined sub strings is not the multiple of str_len, so few characters are left out and these characters may contain ' a '. We have to count these characters.
Now, we need to find the number of a’s in the sub_str. Let count will store number of a's in the sub_str.
Multiplying count with the num_sub_str will give us number of a's in the combined sub strings whose size is less than or equal to str_len and multiple of the size of sub_str. But there are few remaining characters whose count is stored in remaining_str_len. We have to find the occurrence of '*a8' in these characters and increment the count if it is found.
C++ Implementation on Programmercave
Other Competitive Programming Problems and Solutions
Originally published at https://programmercave.com/ on April 24, 2020.
