Max Substring

max_substring_solution.cpp

/*
You are given a string S. Find a string T that has the most number of occurrences as a substring in S.

If the solution is not unique, you should find the one with maximum length. If the solution is still not unique, find the smallest lexicographical one.

cabdab
ab

cabcabc
c

ababababab
ab
*/
#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
using namespace std;


int main() {
	string s; 
	cin >> s;
	int n = (int)s.size();
	vector<int> pos[26];
	// get the positions for all characters
	for (int i = 0; i < n; i += 1) {
		pos[s[i] - 'a'].push_back(i);
	}

	// get the max number of occurences of a character
	int mx_num = 0;
	for (int i = 0; i < 26; i += 1) {
		mx_num = max(mx_num, (int)pos[i].size());
	}

	string mx_answer = "";
	for (int i = 0; i < 26; i += 1) {
		int size = 1;
		if ((int)pos[i].size() != mx_num) {
			continue;
		}

		// make sure we're inside string bounds
		while (pos[i].back() + size < n) {
			// try to expand as long as the characters are equal
			char ch = s[pos[i][0] + size];
			bool ok = true;
			for (auto itr : pos[i]) {
				if (s[itr + size] != ch) {
					ok = false;
				}
			}

			// the end characters are not equal
			if (!ok) {
				break;
			}

			// all good, continue trying to increase size
			size += 1;
		}

		// actually compute a string of length `size` to compare it with the
		// max string
		string c_str = "";
		for (int j = 0; j < size; j += 1) {
			c_str += s[pos[i][0] + j];
		}

		// if the size is bigger or the string is smaller lexicographically
		// update the answer
		if (size >(int)mx_answer.size() || mx_answer > c_str) {
			mx_answer = c_str;
		}
	}

	cout << mx_answer << '\n';
	return 0;
}