## DEV Community is a community of 750,871 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Anurag Pandey

Posted on • Updated on • Originally published at geekypandey.github.io

# Day 1: Rebooting the competitive programming drive

### Disclaimer:

I am a beginner in competitive programming, and this is me documenting my learnings. So, anything I say is just what I think at the moment and should not be taken as hard truths.

It has been a long time now that I practiced my competitive programming skills. Not super good at it. Last I practiced thoroughly was during interview preparation in July 2020.

## Phase 1: Base Building

I have planned to solve at least two `implementation` based problems everyday for a month starting today and additionally learning one new algorithm daily. I personally like string algorithms so I will start from there.

#### Problem 1: Do Not Be Distracted!

``````main() {
int n;
cin >> n;
string s;
cin >> s;
s.erase(unique(begin(s), end(s)), end(s));
sort(begin(s), end(s));
auto it = unique(begin(s), end(s));
if(it != end(s)) cout << "NO";
else cout << "YES";
}
``````

Time Complexity: O(nlog(n))
Space Complexity: O(1) # not considering the space to hold the data

Another solution:

``````main() {
int n;
cin >> n;
string s;
cin >> s;
unordered_set<char> se;
bool yes = true;
for(int i = 0; i < n; i++) {
if(i && s[i] == s[i-1]) continue;
if(se.count(s[i])) {
yes = false;
break;
}
se.insert(s[i]);
}
if(yes) cout << "YES";
else cout << "NO";
}
``````

Time Complexity: O(n)
Space Complexity: O(n) # the `unordered set` used to contain
elements for checking.

#### Problem 2: Black Square

``````main() {
vector<int> v(4);
for(auto& e: v) cin >> e;
string s;
cin >> s;
long long total = 0;
for(auto& c: s) {
int p = c - '0' - 1;  // additional -1 for zero based indexing
total += v[p];
}
cout << total;
}
``````

This would be more fun to write in Python.

``````v = list(map(int, input().split()))
s = input()
s = [int(c)-1 for c in s]  #  -1 for zero based indexing
total = sum(v[i] for i in s)
print(total)
``````

I am sure we could use find STL algorithm for the C++ code.
That is all for today 2 implementation problem solving.

Let us hop on to learning one new/old string algorithm.

### String Algorithm

The basic question when it comes to string is about, whether a given `pattern` of length `m` occurs in a `text` of length `n`.
The problem can be solved using naive method in O(n*m) time.

``````main() {
string text = "abcabc";
string pattern = "abc";
int n = text.length(), m = pattern.length();
bool found = false;
// looping through all starting position of the pattern
for(int i = 0; i < n-m+1; i++) {
// checking if the substring matches
if(text.substr(i, m) == pattern) {
found = true;
break;
}
}
if(found) cout << "YES";
else cout << "NO";
}
``````

Now there are algorithms that can solve the above pattern matching in O(n+m) time. The first one that comes in mind is the famous
`Knuth Morris Pratt` or better known as KMP algorithm.

Here is a video of Donald Knuth talking about KMP algorithm.

``````
vector<int> prefix_func(string s) {
int n = s.length();
vector<int> pi(n, 0);
for(int i = 1; i < n; i++) {
int j = pi[i-1];
while(j > 0 && s[i] != s[j])
j = pi[j-1];
if(s[i] == s[j])
j++;
pi[i] = j;
}
return pi;
}
``````

To use KMP algorithm, pre-compute the table using above `prefix_func`.
So for given `pattern` and `text`, the string that should be passed to `prefix_func` is `pattern + x + text`, where 'x' is some character which doesn't belong to neither pattern nor text.

The different questions that can be answered are:

• Does the pattern occur in the text?
• How many times does the pattern occur in the text?
• If pattern occurs, find the starting position in text.
• Find maximum non-overlapping occurrence of the pattern in the text. And many more.

Most of the time, pattern matching is used as a part for solving a problem, and not a whole problem.

### Resources for additonal learning and practicing:

Dated: 13th July 2021