Prove that any algorithm that has sublinear time have a constant time complexity?
I think to make this work we need to work in a model of computation where the input string is read sequentially. That is, in order to read the $i$'th character of the input string $S$, we first need to read characters number $1,2,\ldots,i-1$. In what follows I also assume that every substring of a valid input is a valid input (this in particular implies the fact that the length of the string cannot be explicitely encoded in, say, the first $O(\log n)$ bits of the input).
Let $S$ be the set of strings such that invoked on any input $x\in S$ the algorithm $A$ reads all of $x$. As the guideline suggests $S$ must be finite, as otherwise $A$ cannot be sublinear.
Now, let $k$ be the length of the longest string in $S$. I claim that $A$ never reads more than $k$ characters of its input. Indeed, suppose there is some input $x$ such that $A$ reads $k'&gt;k$ characters when invoked on $x$. Let $y$ be the string consisting of the first $k'$ characters in $x$ (this is where I use the assumption that every substring of a valid input is a valid input). Because $A$ reads only the first $k'$ characters when invoked on $x$ it cannot distinguish between $x$ and $y$. In particular, it also reads all $k'$ characters when invoked on $y$. Thus, $y\in S$ and $y$ is of size $k'&gt;k$, which contradicts the definition of $k$. We conclude that our assumption was wrong, and $A$ never reads more than $k$ characters of its input.
Because $A$ never reads more than $k$ characters of the input, it has a finite (constant) number of distinct possible executions. Thus, its worst-case time-complexity is also constant.
(I implicitly assumed a deterministic model of computation here, but it isn't hard to make the argument work under the presence of randomness, both for worst-case and expected time-complexity)