text:
Counting Fibonacci Orbits
If we define a Fibonacci-like sequence as fk(n) = (fk(n-1) + fk(n-2)) % k, for some integer k (where % is the modulo operator), the sequence will necessarily be cyclic, because there are only k2 different values for (fk(n-1), fk(n-2)). However, this cycle doesn't usually include all possible pairs of values, so depending on the two starting values fk(0) and fk(1), we might get different cycles. For example, for k = 2, we have the following four possibilities, depending on the first two values:
0, 0, 0, 0, 0, 0, 0, 0, 0, ...
0, 1, 1, 0, 1, 1, 0, 1, 1, ...
1, 0, 1, 1, 0, 1, 1, 0, 1, ...
1, 1, 0, 1, 1, 0, 1, 1, 0, ...

Due to the cyclic nature of the sequences, there are really only two fundamentally different sequences here, with orbits (0) and (0, 1, 1). Let's look at k = 3:
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...
0, 1, 1, 2, 0, 2, 2, 1, 0, 1, 1, 2, 0, 2, 2, 1, ...
0, 2, 2, 1, 0, 1, 1, 2, 0, 2, 2, 1, 0, 1, 1, 2, ...
1, 0, 1, 1, 2, 0, 2, 2, 1, 0, 1, 1, 2, 0, 2, 2, ...
1, 1, 2, 0, 2, 2, 1, 0, 1, 1, 2, 0, 2, 2, 1, 0, ...
1, 2, 0, 2, 2, 1, 0, 1, 1, 2, 0, 2, 2, 1, 0, 1, ...
2, 0, 2, 2, 1, 0, 1, 1, 2, 0, 2, 2, 1, 0, 1, 1, ...
2, 1, 0, 1, 1, 2, 0, 2, 2, 1, 0, 1, 1, 2, 0, 2, ...
2, 2, 1, 0, 1, 1, 2, 0, 2, 2, 1, 0, 1, 1, 2, 0, ...

Again, there are only two different orbits: (0) and (0, 1, 1, 2, 0, 2, 2, 1).
For higher k we might get more orbits, but they will still fall into a comparably small number of classes. For example k = 4 yields the four orbits (0), (0,1,1,2,3,1), (0, 2, 2), (0, 3, 3, 2, 1, 3) and k = 5 the three orbits (0), (0, 1, 1, 2, 3, 0, 3, 3, 1, 4, 0, 4, 4, 3, 2, 0, 2, 2, 4, 1) and (1, 3, 4, 2).
Your task in this challenge is to compute how many orbits the sequence generates for a given k. This is OEIS A015134. Here are the first 100 values (starting from k = 1):
1, 2, 2, 4, 3, 4, 4, 8, 5, 6, 14, 10, 7, 8, 12, 16, 9, 16, 22, 16,
29, 28, 12, 30, 13, 14, 14, 22, 63, 24, 34, 32, 39, 34, 30, 58, 19,
86, 32, 52, 43, 58, 22, 78, 39, 46, 70, 102, 25, 26, 42, 40, 27, 52,
160, 74, 63, 126, 62, 70, 63, 134, 104, 64, 57, 78, 34, 132, 101, 60,
74, 222, 37, 38, 62, 328, 89, 64, 82, 124, 41, 86, 42, 172, 75, 44,
184, 178, 181, 132, 82, 180, 99, 140, 104, 246, 49, 50, 114, 76

Make sure to check k = 11, which is the first input which yields more than k orbits.
Rules
You're given a positive integer k and should output A015134(k).
You may write a program or a function and use any of the standard methods of receiving input and providing output.
You may use any programming language, but note that these loopholes are forbidden by default.
This is code-golf, so the shortest valid answer – measured in bytes – wins.

This is close enough to https://codegolf.stackexchange.com/q/26578/194 that I won't close it unilaterally but I would cast the 5th vote to close as dupe.

Husk, 17 16 bytes
Lüȯ€U¡ȯ↔m%⁰∫π2ŀ⁰

Try it online!
Explanation
Lüȯ€U¡ȯ↔m%⁰∫π2ŀ⁰  Implicit input, say n=4.
              ŀ⁰  Lowered range: [0,1,2,3]
            π2    Cartesian second power: [[0,0],[0,1],[1,0],[0,2]..
 üȯ                Deduplicate with respect to this function:
   €U¡ȯ↔m%⁰∫       Arguments are two pairs, say a=[0,2], b=[1,1]
     ¡ȯ            Iterate on a:
           ∫       Cumulative sum,
        m%⁰        take modulo n of each,
       ↔           then reverse: [[0,2],[2,0],[2,2],[0,2],[2,0]..
    U              Cut at first repeated element: [[0,2],[2,0],[2,2]]
   €               Is b in this list? No, so they are distinct in ü.
L                 Number of remaining pairs.

Haskell, 196 191 bytes
import Data.List
o(a:b)=1+o[x|x<-b,not$(0<$a)==(0<$x)&&isInfixOf a(x++x)]
o _=0
k#(a,b)=(b,mod(a+b)k)
p!(a:b)|elem a p=fst<$>p|r<-p++[a]=r!b
f k=o[[]!iterate(k#)(a,b)|a<-[0..k-1],b<-[0..k-1]]

Try it online!
This could probably be improved. Particularly if someone can find a way to avoid isInfixOf and remove the import.
Basic idea is to generate a list of "states" (tuples containing the two previous values) to see when it starts to cycle. Then we check whether each orbit is different to its predecessors (really works the other way around but it's hard to put into words). To check if orbits are the same we check if the length is the same and whether one fits into the other concatenated with itself. For example [0,2,2],[2,2,0]: length of both is 3 and [0,2,2,0,2,2] contains [2,2,0] as a continuous subsequence. I'm not sure if it's foolproof but it seems to work.
EDIT: thanks to Laikoni for taking off 5 bytes! I should've read more of those tips.

It looks like you can use this tip to avoid length. Another byte can be saved in ! with |r<-p++[a]=r!b.

Jelly, 17 bytes
Ṛ+\%³
Ḷṗ2ÇÐĿ€Ṣ€QL

Try it online!

Bash, 172, 119, 113, 91 bytes
n=$1;for((k=0;k<n*n;++k)){((H[k]||++c));for((;!H[k];k=(k/n+k)%n*n+k/n)){ H[k]=1;};};echo $c

Try it online

Wolfram Language (Mathematica), 76 70 bytes
Tr[EdgeCycleMatrix[#->{#[[2]],Tr@#~Mod~n}&/@Tuples[Range[n=#]-1,2]]!]&

Try it online!
How it works
We construct the graph given by the rules {{0,0}->{0,0}, {1,0}->{1,1}, ...} that, given two elements of a generalized Fibonacci sequence, find the next one modulo n. The EdgeCycleMatrix gives the incidence matrix from cycles to edges in this graph; we want to count its rows.
(There are a number of built-ins that do a similar task, but ConnectedComponents is longer, and FindCycle needs lots of extra inputs to make it work. Besides, EdgeCycleMatrix is a rectangular array, not funny-shaped like the other two, which helps later.)
To count the rows of the matrix, we take the factorial of the entries to turn it into a matrix of all ones, then take the trace. (Each cycle contains at least one edge and therefore there are at least as many columns as rows - so this counts the rows and not the columns.)

MATL, 38 36 bytes
:qt!J*+le"@GU:"t&Zjwy+G\J*+hu]S]Xhun

Try it online! It times out in the online compiler for input exceeding 7.
Explanation
The code defines orbits in terms of complex numbers, where the imaginary part is the new term and the real part is the preceding term in the Fibonacci sequence. Each complex value encodes the state of the sequence. Namely, given a+jb the next value is computed as b+j(a+b).
The possible starting values are a+jb with a, b in [0, 1, ..., k-1]. For each starting value, the code iterates k^2 times. Actually, to make the code shorter, each iteration is applied to all accumulated so values so far, and the results are deduplicated (which would be necessary at the end anyway). After the last iteration, the vector of deduplicated complex values is sorted (by absolute value, then by angle). This gives a "signature" for each orbit.
At the end of the program, signatures are collected into a cell array. The number of unique signatures is the desired output.
:q          % Implicit input: k. Push row vector [0, 1, ..., k-1]
t!          % Duplicate, transpose: gives column vector [0; 1; ...; k-1]
J*+         % Multiply by 1j, add with broadcast. Gives a k × k matrix of
            % values a+jb with a, b in [0, 1, ..., k-1]
le          % Linearize into a row vector
"           % For each c in that vector
  @         %   Push c
  GU:"      %   Do the following k^2 times
    t&Zj    %     Duplicate and split into real and imaginary parts: a, b
    wy+     %     Swap, duplicate, from below, add: transforms a, b into
            %     b, a+b. This is the basic step in the Fibonacci sequence
            %     In subsequent iterations a and b may be vectors instead
            %     of numbers, as they include all values obtained so far
    G\      %     Modulo k, element-wise
    J*+     %     Times 1j, add. Gives the next complex number for each of
            %     the complex numbers so far
    hu      %     Append to values so far and deduplicate. This may extend
            %     the vector of complex numbers
  ]         %   End
  S         %   Sort
]           % End
Xh          % Collect entire stack into a cell array
u           % Deduplicate
n           % Number of entries. Implicit display

Perl 5, 80+1 (-p) bytes
$n=$_;map{$a[$_]||++$\;$a[$_]++until$a[$_=0|($_/$n+$_)%$n*$n+$_/$n]}0..$n**2-1}{

Try it online

JavaScript (ES6), 102 bytes
k=>F=(a=0,b=0,C=0,q)=>q?F[q=[a,b%=k]]?0:1|F(b,a+b,C,F[q]=1):b<k?F(a,b+1,C+F(a,b,C,1)):++a<k?F(a,0,C):C

Returns a function which returns the result. For 3 more bytes we can have it return the result directly:
k=>(F=(a,b,C,q)=>q?F[q=[a,b%=k]]?0:1|F(b,a+b,C,F[q]=1):b<k?F(a,b+1,C+F(a,b,C,1)):++a<k?F(a,0,C):C)(0,0,0)

Both have time complexity O(n2).

Python 2, 214 bytes
def h(k):
 R=[]
 for p in[[i/k,i%k,(i/k+i%k)%k]for i in range(k*k)]:
	while p[:2]!=p[-2:]:
		p.append(sum(p[-2:])%k)
	p=p[:-2]
	if not any([p==x[i:]+x[:i]for i in range(len(p))for x in R]):R.append(p)
 print len(R)

Try it online!
It's not very efficient but it's the golfiest I could do.

JavaScript (ES6), 337 335 bytes
Sorry for the Ω(k^3) brute-force algorithm.
(k,x=o=0,u=[],s=(q,w,v,j=d=0)=>{while(j++<v)d|=q.reduce((a,b,i)=>a&=b==w[(i+j)%v],1);return d})=>{for(;x<k;x++)for(y=0;y<k;y++){l=2;r=[x,y];do{r.push((c=(d=r[(l+=2)-3])+r[l-4])%k,(c+d)%k)}while(!(t=r.slice(0,h=l/2)).reduce((a,b,i)=>a&=b==r[i+h],1));if(!u.reduce((q,z)=>q|=(t.length-(a=z.length)?0:s(t,z,a)),0)){o++;u.push(t)}}return o}

The performance... When I was calculating A015134(something beyond k=50) it exceeded 60s limit on TIO.

var g=(k,x=o=0,u=[],s=(q,w,v,j=d=0)=>{while(j++<v)d|=q.reduce((a,b,i)=>a&=b==w[(i+j)%v],1);return d})=>{for(;x<k;x++)for(y=0;y<k;y++){l=2;r=[x,y];do{r.push((c=(d=r[(l+=2)-3])+r[l-4])%k,(c+d)%k)}while(!(t=r.slice(0,h=l/2)).reduce((a,b,i)=>a&=b==r[i+h],1));if(!u.reduce((q,z)=>q|=(t.length-(a=z.length)?0:s(t,z,a)),0)){o++;u.push(t)}}return o}

for (var ix = 1; ix <= 15; ix++)
 console.log(`A015134(${ix}) = ${g(ix)}`);

Explanation(Ungolfed)
function CheckIfSameOrbit(Array_1, Array_2, Length) { // Checks if the orbits are equal
  var d = false, j = 0;                               // Assume both have same length
  while (j < v) {                                     // Checks for different startings
    j++;
    d |= Array_1.reduce(function(Acc, Item, Index) {  // Element-by-element comparison
      Acc &= Item == w[(Index + j) % v], 1);
    });                                               // Return true if any starting
  }                                                   // point makes two orbits identical
}

function A015134(k) {                                 // Main Program
  var o = 0, u = [];
  for (var x = 0; x < k; x++) {                       // Checks different pairs of (x, y)
    for (var y = 0; y < k; y++) {
      var l = 2, r = [x, y], h = 1, t;
      do {                                            // Find until a complete orbit is
        l += 2;                                       // found (except for (0, 0) case)
        h = l / 2;
        var d = r[l - 3], c = r[l - 3] + r[l - 4];
        r.push(c % k, (c + d) % k);
        t = r.slice(0, h);
      }
      while (!t.reduce(function(Acc, Item, Index) {   // Which is, if 2 identical copies
        Acc &= Item == r[Index + h];                  // of the orbit are calculated
      }, 1));

      if (!u.reduce(function(Acc, Item) {             // If the orbit is a new one
        var a = Item.length;
        Acc |= (t.length - a ? 0 : s(t, Item, a));
      }, 0)) {
        o++;                                          // Increment the counter, and
        u.push(t);                                    // record it to the list
      }
    }
  }
  return o;                                           // Ultimately return the counter;
}


text:
Downgrade to a Palindrome
Given a string s, return the smallest contiguous substring you can remove to create a palindrome.

Examples:
800233008   -> 2
racecarFOOL -> FOOL
abcdedcba   -> (empty string)
ngryL Myrgn -> "L " (or " M")
123456789   -> 12345678 (or 23456789)
aabcdbaa    -> c (or d)
[[]]        -> [[ (or ]])
a           -> (empty string)

Test case suggestions from users (if you find an edge case not listed, please post a comment):
aabaab      -> b    | Suggested by Zgarb, some returned "aa".

Rules

Only printable ASCII characters will appear in the input (no newlines, keep it simple).
Not really a rule, but note <>, /\, (), [] and {} are not palindromes.

This is code-golf, smallest byte-count wins.

+100 bounty has been claimed by Adnan

Tesf case: aabaab

I think it will help keep questions accessible to more visitors if ingroup jargon like “CMC” is avoided (looking it up, it appears to stand for “chat mini challenge”, which I imagine means a small challenge posted in the chat room associated with this site).

Isn't [[]] a palindrome?

@Carl It may look like one, but when you reverse the characters, you get ]][[. Consider that aabb is the same thing, just different characters.

@ConorO'Brien oooh, yes :)

@ShreevatsaR fixed.

What about qrabbapo? Then you need to remove from two sides, gr and po to obtain abba, or it would be considered as removing qrabbap or rabbapo?

@JavaGonzalezArribas the answer would be qrabbap or rabbapo, you must remove a single, contiguous substring.

7/12? if that is 2017-12-07, what kind of locale are you using? If that is 2018-07-12, that is a long way off...

@NH 7/12 is dec 7 in many european countries. Mine for instance

"(will be awarded 7/12)" huh?

see? I'm not the only one confused.  You didn't specify a locale, so please use a less ambiguous date (like the ISO 8601 version: 2017-12-07)

@EriktheOutgolfer HE MUST GO BACK IN TIME TO CLAIM THIS REWARD. Kidding, no idea what the heck I did there.

@NH. No, it's not that. 7/12 can either mean December 7 or July 12, both of which can't be applicable in any case. ;)

Jelly, 16 bytes
Ḣ;Ṫµ=Ṛ
0,0jŒṖÇÞṪ

Try it online!
How it works
0,0jŒṖÇÞṪ  Main link. Argument: s (string)

0,0j       Join [0, 0], separating by s. This prepends and appends a 0 to s.
    ŒṖ     Build all partitions of the resulting array.
      ÇÞ   Sort the partitions by the helper link.
           As a side effect, this will remove the first and last element of each
           partition. The 0's make sure that not removing any characters from s
           will still remove [0] from both sides.
        Ṫ  Tail; extract the last one.

Ḣ;Ṫµ=Ṛ     Helper link. Argument: A (array/partition)

Ḣ          Head; yield and remove the first chunk of A.
  Ṫ        Tail; yield and remove the last chunk of A.
 ;         Concatenate head and tail.
   µ=Ṛ     Compare the result, character by character, with its reverse.
           A palindrome of length l will yield an array of l 1's, while a
           non-palindrome of length l will yield an array with at least one 0 among
           the first l/2 Booleans. The lexicographically largest result is the one
           with the longest prefix of 1's, which corresponds to the longest
           palindrome among the outfixes.

J, 24 bytes
(0{::(-:|.)\.#&,<\)~i.@#

Try it online!
Explanation
(0{::(-:|.)\.#&,<\)~i.@#  Input: array of chars S
                       #  Length of S
                    i.@   Range, [0, 1, ..., len(S)-1]
(                 )~      Dyadic verb on range and S
           \.               For each outfix of S of size x in range
        |.                    Reverse
      -:                      Matches input (is palindrome)
                <\          Box each infix of S of size x in range
             #&,            Flatten each and copy the ones that match
 0{::                       Fetch the result and index 0 and return

Perhaps you might want to choose (;&quote f)&> as the test harness verb?

Wolfram Language (Mathematica), 53 51 bytes
Byte count assumes CP-1252 encoding.
±{a___,Shortest@b___,c___}/;PalindromeQ[a<>c]:={b}

Try it online!
Defines a unary operator ± (or a function PlusMinus). Input and output are lists of characters. The test suite does the conversion from and to actual strings for convenience.

Is Reverse then comparing that reverse to the original shorter than PalindromeQ? I don't know Mathematica, so no idea.

Good answer, but shouldn't one account for the splitting of strings and joining them back together in your character count?  Characters@#/.{a___,Shortest@b___,c___}/;PalindromeQ[a<>c]:>b~~""&

@MagicOctopusUrn Reverse[x={a,c}]==x is two bytes longer. I don't know whether there's any shorter alternative.

@KellyLowder Lists of characters are valid representations of strings on PPCG. It's a bit awkward in Mathematica, where you wouldn't normally use that representation, but it's still valid. I'll dig up a meta post.

@KellyLowder I think this is the accepted policy. The main reason why it's awkward in Mathematica is that Mathematica doesn't have an actual character type, so the characters end up being singleton strings.

OK, just asking.  I've put some posts on here that included the string splitting and concatenation.  If that's deemed unnecessary, so be it.

@MartinEnder I'm not sure if a list of singleton strings is allowed though, FryAmTheEggman's answer seems to have a score of -1.

05AB1E, 18 bytes
ā<Œ¯¸«ʒRõsǝÂQ}éнèJ

Uses the 05AB1E encoding. Try it online!

Interesting usage of filter there... We were trying to do an "a without b" type of deal, but if there was two instances of the substring, we'd get false negatives. Feels like we were over-complicating it now that I see this lol. Noice, I'll give you a 100 bounty in 2 days.

ǝ was seriously genius though.

Jelly, 20 bytes
ŒḂ⁹Ƥ
çÐ€JN$Ẏi1ịẆẋ⁻Ṛ$

Try it online!

Python 3, 97 bytes
f=lambda s,p='	':min([s][:p[::-1]in p+p]+(s and[f(s[1:],p+s[0]),f(s[:-1],s[-1]+p)]or[p]),key=len)

Try it online!

Python 2, 116 bytes
def f(i):R=range(len(i)+1);print min([i[y:k+1]for y in R for k in R if(i[:y]+i[k+1:])[::-1]==i[:y]+i[k+1:]],key=len)

Try it online!
Saved a couple of bytes with help from Halvard Hummel!

117 bytes

@HalvardHummel Thanks, I was planning to change that too but didn’t have an internet connection for the last 2 hours.

Bash, 108 bytes
for((j=0;;j++)){
for((i=0;i<${#1};i++)){
r=${1:0:i}${1:j+i}
[[ $r = `rev<<<$r` ]]&&echo "${1:i:j}"&&exit
}
}

Takes input as command-line argument.
Try it online! with quotes printed around the output for viewing leading/trailing spaces.

Prolog, 271 byte
p([_]).
p([X,X]).
p([X|Y]):-append([P,[X]],Y),p(P).

s(P,M,S,R,N):-p(P),append([M,S],N).
s(P,M,S,S,N):-p(S),append([P,M],N).
s(P,M,S,P,M):-append([P,S],X),p(X).

d(Y,P,N):-
    findall([A,B,C],(append([R,M,X],Y),s(R,M,X,B,C),length(B,A)),S),
    sort(1,@>,S,[[_,P,N]|_]).

At some point I realized this is going to be huge by code-golf standards, so I kept a few extra blank spaces to preserve the resemblance to the non-obfuscated version.  But I still think it might be interesting since it's a different approach to the problem.
The non-obfuscated version:
palindrome([_]).
palindrome([X, X]).
palindrome([X | Xs]) :-
    append([Prefix, [X]], Xs),
    palindrome(Prefix).

palindrome_split(Prefix, Mid, Suffix, Prefix, N) :-
    palindrome(Prefix),
    append([Mid, Suffix], N).
palindrome_split(Prefix, Mid, Suffix, Suffix, N) :-
    palindrome(Suffix),
    append([Prefix, Mid], N).
palindrome_split(Prefix, Mid, Suffix, P, Mid) :-
    append([Prefix, Suffix], P),
    palindrome(P).

palindrome_downgrade(NP, P, N):-
    findall(
        [La, Pa, Na],
        (append([Prefix, Mid, Suffix], NP),
         palindrome_split(Prefix, Mid, Suffix, Pa, Na),
         length(Pa, La)),
        Palindromes),
    sort(1, @>, Palindromes, [[_, P, N] | _]).

C++, 254 248 246 bytes
-6 bytes thanks to Zacharý
-2 bytes thanks to Toby Speight
#include<string>
#define S size()
#define T return
using s=std::string;int p(s t){for(int i=0;i<t.S;++i)if(t[i]!=t[t.S-i-1])T 0;T 1;}s d(s e){if(!p(e))for(int i,w=1;w<e.S;++w)for(i=0;i<=e.S-w;++i){s t=e;t.erase(i,w);if(p(t))T e.substr(i,w);}T"";}

So...

I used T as a macro definition because doing R"" as another effect on string literal ( it's a prefix used to define raw string literals, see cppreference for more informations ) that is not there when i do T""
Preprocessor definitions can't be on the same line, and have to have at least one space between the name and the content in the definition
2 functions : p(std::string) to test if the string is a palindrome. If it is, it returns 1 which casts to true, else it returns 0, which casts to false
The algorithm loops over the whole string testing if it's a palindrome when erasing each time 1 element, then test erasing 2 elements ( loops over that to the maximum size of the string ), from the first index to the last index - number of erased char. If it finds erasing some part is a palindrome, then, it returns. For example, when passing the string "aabcdbaa" as parameter, both c and d are valid answer, but this code will return c because erasing it and testing if it's a palindrome comes before testing if erasing d and testing if it's palindrome
Here is the code to test :
std::initializer_list<std::pair<std::string, std::string>> test{
    {"800233008","2"},
    { "racecarFOOL","FOOL" },
    { "abcdedcba","" },
    { "ngryL Myrgn","L " },
    { "123456789","12345678" },
    { "aabcdbaa","c" },
    { "[[]]","[[" },
    { "a","" },
    { "aabaab","b" }
};

for (const auto& a : test) {
    if (a.second != d(a.first)) {
        std::cout << "Error on : " << a.first << " - Answer : " << a.second  << " - Current : " << d(a.first) << '\n';
    }
}

Would this work for the last line? using s=std::string;int p(s t){for(int i=0;i<t.S/2;++i)if(t[i]!=t[t.S-i-1])T 0;T 1;}s d(s e){if(!p(e))for(int i,w=1;w<e.S;++w)for(i=0;i<=e.S-w;++i){s t=e;t.erase(i,w);if(p(t))T e.substr(i,w);}T"";}

Can the /2 be omitted?  Iterating over the whole length will simply repeat the tests we've done, which should be harmless.  You might want to expand what you mean by the "other effect" of R"" (i.e. it's parsed as a raw string literal).

I've modified this and added the result as an answer of my own.

Japt, 26 22 bytes
¬£¬ËUjEY ê¬©UtEY
c æ+0

Test it online! Trying to figure out how to map false to something falsy and any string to something truthy in one byte. Currently I'm using +0...

Haskell, 98 94 81 80 bytes
""#0
(h#n)t|(==)=<<reverse$h++drop n t=take n t|x:r<-t=(h++[x])#n$r|m<-n+1=t#m$h

Try it online! Example usage: ""#0 $ "aabaab" yields "b".
Edit: -1 byte thanks to  Ørjan Johansen.

You can replace the last "" by t.

JavaScript, 90 bytes
a=>a.map((_,p)=>a.map((_,q)=>k||(t=(b=[...a]).splice(q,p),k=''+b==b.reverse()&&t)),k=0)&&k

Try it online!

f=
a=>a.map((_,p)=>a.map((_,q)=>k||(t=(b=[...a]).splice(q,p),k=''+b==b.reverse()&&t)),k=0)&&k

F=a=>console.log(a.padEnd(11)+' ---> '+f([...a]).join``)
F('800233008')
F('racecarFOOL')
F('abcdedcba')
F('ngryL Myrgn')
F('123456789')
F('aabcdbaa')
F('[[]]')
F('a')
F('aabaab')

TSQL (2016) 349B
Not the most compact but straightforward solution:
DECLARE @i VARCHAR(255)='racecarFOOL'
;WITH DAT(v,i,l)AS(SELECT value,(ROW_NUMBER()OVER(ORDER BY value))-1,LEN(@i)FROM STRING_SPLIT(REPLICATE(@i+';',LEN(@i)+1),';')WHERE value<>'')
SELECT TOP 1C,S
FROM(SELECT LEFT(D.v, D.i)+SUBSTRING(D.v,D.i+E.i+1,D.l)C,SUBSTRING(D.v,D.i+1,E.i)S
FROM DAT D CROSS APPLY DAT E)C
WHERE C=REVERSE(C)
ORDER BY LEN(C)DESC

You can use @ as a variable for a few bytes.  In the CTE you can use where''=value) for another one and you don't need to return C in the result.

C++, 189 186 176 167 bytes
I started with HatsuPointerKun's answer, changing the test to simply compare equality with reversed string; then I changed how we enumerate the candidate strings.  Following this, the macros were only used once or twice each, and it was shorter to inline them.
#include<string>
using s=std::string;s d(s e){for(int i,w=0;;++w){s t=e.substr(w);for(i=-1;++i<=t.size();t[i]=e[i])if(t==s{t.rbegin(),t.rend()})return e.substr(i,w);}}

Explanation
Equivalent readable code:
std::string downgrade(std::string e)
{
    for (int w=0; ; ++w) {
        std::string t = e.substr(w);
        for (int i=0;  i<=t.size();  ++i) {
            if (t == std::string{t.rbegin(),t.rend()})
                // We made a palindrome by removing w chars beginning at i
                return e.substr(i,w);
            t[i] = e[i];  // next candidate
        }
    }
}

The enumeration of candidates begins by initialising a string with the first w characters omitted, and then copying successive characters from the original to move the gap.  For example, with the string foobar and w==2:
foobar
  ↓↓↓↓
  obar

foobar
↓
fbar

foobar
 ↓
foar

foobar
  ↓
foor

foobar
   ↓
foob

The first pass (with w==0) is a no-op, so the full string will be considered over and over again.  That's fine - golfing trumps efficiency!  The last iteration of this loop will access the one-past-the-end index; I seem to get away with that with GCC, but strictly, that's Undefined Behaviour.
Test program
A direct lift from HatsuPointerKun's answer:
static const std::initializer_list<std::pair<std::string, std::string>> test{
    { "800233008", "2" },
    { "racecarFOOL", "FOOL" },
    { "abcdedcba", "" },
    { "ngryL Myrgn", "L " },
    { "123456789", "12345678" },
    { "aabcdbaa", "c" },
    { "[[]]", "[[" },
    { "a","" },
    { "aabaab", "b" }
};

#include <iostream>
int main()
{
    for (const auto& a : test) {
        if (a.second != d(a.first)) {
            std::cout << "Error on: " << a.first
                      << " - Expected: " << a.second
                      << " - Actual: " << d(a.first) << '\n';
        }
    }
}

Suggest rbegin(x) and rend(x) instead of x.rbegin() and x.rend()

I think the associated #include<iterator> will outweigh the gains.

Husk, 18 bytes
◄LfmS=↔†!⁰ṠM-Qŀ⁰Q⁰

Try it online!
Explanation
◄LfmS=↔†!⁰ṠM-Qŀ⁰Q⁰  Input is a string, say s="aab"
              ŀ⁰    Indices of s: x=[1,2,3]
             Q      Slices: [[],[1],[1,2],[2],[1,2,3],[2,3],[3]]
          ṠM-       Remove each from x: [[1,2,3],[2,3],[3],[1,3],[],[1],[1,2]]
       †!⁰          Index into s: ["aab","ab","b","ab","","a","aa"]
   mS=↔             Check which are palindromes: [0,0,1,0,1,1,1]
  f             Q⁰  Filter the slices of s by this list: ["aa","aab","ab","b"]
◄L                  Minimum on length: "b"

Jelly, 33 bytes
r/ḟ@J}ị
“”µJp`ç³$ŒḂ$Ðfạ/ÞḢr/ịµŒḂ?

Try it online!

JavaScript (ES6), 91 78 bytes
(s,i=0,j=0,S=[...s],b=S.splice(i,j))=>S+''==S.reverse()?b:f(s,s[++i]?i:!++j,j)

Input and output are lists of characters.
Recursively removes a larger and larger slice from the input until a palindrome is found.
Snippet:

f=
(s,i=0,j=0,S=[...s],b=S.splice(i,j))=>S+''==S.reverse()?b:f(s,s[++i]?i:!++j,j)

console.log(f([...'800233008']).join``)   // 2
console.log(f([...'racecarFOOL']).join``) // FOOL
console.log(f([...'abcdedcba']).join``)   // (empty string)
console.log(f([...'ngryL Myrgn']).join``) // "L " (or " M")
console.log(f([...'123456789']).join``)   // 12345678 (or 23456789)
console.log(f([...'aabcdbaa']).join``)    // c (or d)
console.log(f([...'[[]]']).join``)        // [[ (or ]])
console.log(f([...'a']).join``)           // (empty string)

PHP 104+1 bytes
while(~($s=$argn)[$e+$i++]?:++$e|$i=0)strrev($t=substr_replace($s,"",$i,$e))==$t&&die(substr($s,$i,$e));

Run as pipe with -nR or try it online.

Perl 5, 72 +1 (-p) bytes
$\=$_;/.*(?{$,=$`.$';$\=$&if length$&<length$\&&$,eq reverse$,})(?!)/g}{

Try it online

Haskell, 109 105 bytes
snd.minimum.([]#)
p#s@(a:b)=[(i,take i s)|i<-[0..length s],(==)<*>reverse$p++drop i s]++(p++[a])#b
p#_=[]

Try it online!
EDIT: Thanks @H.PWiz for taking off 4 bytes! I need to get better with those monads!

REXX, 132 bytes
a=arg(1)
l=length(a)
do i=1 to l
  do j=0 to l-i+1
    b=delstr(a,i,j)
    if b=reverse(b) & m>j then do
      m=j
      s=substr(a,i,j)
      end
    end
  end
say s

Ruby, 86 84 bytes
->s{l=i=0
(l+=(i+=1)/z=s.size-l+1
i%=z)while(w=s[0,i]+s[i+l..-1])!=w.reverse
s[i,l]}

Try it online!

Saved 2 bytes thanks to Cyoce

You don't need the parentheses around z=s.size-l+1.

@Cyoce Thank you. I have a hard time remembering all the operator precedence.

C (gcc), 307 bytes
#define T malloc(K)
P(S,i,y,z,k,u,L,K,V)char*S;{char*M,*R,*E;K=strlen(S);M=T;R=T;E=T;for(i=0;i<K;++i){for(y=0;y<=K-i;++y){strcpy(M,S);for(z=y;z<y+i;E[z-y]=M[z],++z);for(k=y;k+i<=K;M[k]=M[k+i],++k);V=strlen(M);strcpy(R,M);for(u=0;u<V/2;L=R[u],R[u]=R[V-u-1],R[V-u-1]=L,++u);if(!strcmp(M,R))puts(E),exit(0);}}}

Try it online!

259 bytes

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/

sort: votes


text:
Do we share the prime cluster?
The prime cluster of an integer N higher than 2 is defined as the pair formed by the highest prime strictly lower than N and the lowest prime strictly higher than N.
Note that following the definition above, if the integer is a prime itself, then its prime cluster is the pair of the primes preceding and succeeding it.
Task
Given two integers integers N, M (N, M ≥ 3), output a truthy / falsy value based on whether N and M have the same prime cluster.
This is code-golf, so the aim is to reduce your byte count as much as possible. Thus, the shortest code in every programming language wins.
Test cases / Examples
For instance, the prime cluster of 9 is [7, 11], because:

7 is the highest prime strictly lower than 9, and
11 is the lowest prime strictly higher than 9.

Similarly, the  the prime cluster of 67 is [61, 71] (note that 67 is a prime).
Truthy pairs

8, 10
20, 22
65, 65
73, 73
86, 84
326, 318
513, 518

Falsy pairs

4, 5
6, 8
409, 401
348, 347
419, 418
311, 313
326, 305

Do the truthy / falsy values have to be two distinct values or can one define a mapping from their program's output to a truthy / falsy value and output (potentially infinitely) many different values?

@JonathanFrech Truthy/Falsy per [tag:decision-problem] definition, not necessarily consistent but distict and truthy/falsy

Jelly, 6 4 3 5 4 bytes
rÆPE

Try it online! or Try all test cases.
How it works
rÆPE    Main link. Arguments: N, M
r       Yield the range of integers between N and M, inclusive.
 ÆP     For each integer, yield 1 if it is prime, 0 otherwise.
   E    Yield 1 if all items are equal (none in the range were prime,
        or there's only one item).

Works because two numbers have different prime clusters iff there is a prime between them, or either number is itself prime; unless both numbers are the same, in which case E returns 1 anyway (all items in a single-item array are equal).

Your programs source doesn’t look friendly...

C (gcc), 153 146 bytes
i,B;n(j){for(B=i=2;i<j;)B*=j%i++>0;return!B;}
#define g(l,m,o)for(l=o;n(--l););for(m=o;n(++m););
a;b;c;d;h(e,f){g(a,b,e)g(c,d,f)return!(a-c|b-d);}

-7 from Jonathan Frech
Defines a function h which takes in two ints and returns 1 for truthy and 0 for falsey
Try it online!
n is a function that returns 1 if its argument is not prime.
g is a macro that sets its first and second arguments to the next prime less than and greater than (respectively) it's third argument
h does g for both inputs and checks whether the outputs are the same.

return a==c&&b==d; can be return!(a-c|b-d);.

146 bytes.

@JonathanFrech Fixed the TIO link.

JavaScript (ES6), 57 56 bytes
Takes input in currying syntax (a)(b). Returns 0 or 1.
a=>b=>a==b|!(g=k=>a%--k?g(k):k<2||a-b&&g(a+=a<b||-1))(a)

Test cases

let f =

a=>b=>a==b|!(g=k=>a%--k?g(k):k<2||a-b&&g(a+=a<b||-1))(a)

console.log('Truthy')
console.log(f(8)(10))
console.log(f(20)(22))
console.log(f(65)(65))
console.log(f(73)(73))
console.log(f(86)(84))
console.log(f(326)(318))
console.log(f(513)(518))

console.log('Falsy')
console.log(f(4)(5))
console.log(f(6)(8))
console.log(f(409)(401))
console.log(f(348)(347))
console.log(f(419)(418))
console.log(f(311)(313))

How?
a => b =>                 // given a and b
  a == b |                // if a equals b, force success right away
  !(g = k =>              // g = recursive function taking k
    a % --k ?             //   decrement k; if k doesn't divide a:
      g(k)                //     recursive calls until it does
    :                     //   else:
      k < 2 ||            //     if k = 1: a is prime -> return true (failure)
      a - b &&            //     if a equals b: neither the original input integers nor
                          //     any integer between them are prime -> return 0 (success)
      g(a += a < b || -1) //     else: recursive call with a moving towards b
  )(a)                    // initial call to g()

R, 63 46 bytes
-17 by Giuseppe
function(a,b)!sd(range(numbers::isPrime(a:b)))

Try it online!
Pretty simple application of ETHProductions' Jelly solution. Main interesting takeaway is was that with R boolean vectors any(x)==all(x) is equivalent to min(x)==max(x).

this tip for golfing in R is applicable here; and TIO has numbers installed instead

Also, since min(x)==max(x) is equivalent to checking that all elements in is_prime(a:b) are equal, we can use this last trick to get it down to 46 bytes with either the primes or the numbers package.

PARI/GP, 28 bytes
v->s=Set(v);#s<2||!primes(s)

Try it online with all test cases!
Returns 0 or 1 (usual PARI/GP "Boolean" values).
Explanation:
v must be a vector (or a column vector, or a list) with the two numbers N and M as coordinates. For example [8, 10]. Then s will be the "set" made from these numbers, which is either a one-coordinate vector (if N==M), or a two-coordinate vector with sorted entries otherwise.
Then if the number #s of coordinates in s is just one, we get 1 (truthy). Otherwise, primes will return a vector of all primes in the closed interval from s[1] to s[2]. Negation ! of that will give 1 if the vector is empty, while negation of a vector of one or more non-zero entries (here one or more primes) will give 0.

Python 3, 103 95 91 bytes
lambda*z:len({*z})<2or[1for i in range(min(z),max(z)+1)if all(i%k for k in range(2,i))]<[0]

Try it online!

Perl 6, 52 bytes
{[eqv] @_».&{(($_...0),$_..*)».first(*.is-prime)}}

Test it
Expanded:
{  # bare block lambda with implicit slurpy input ｢@_｣

  [eqv]               # see if each sub list is equivalent

    @_».&{            # for each value in the input

      (

        ( $_ ... 0 ), # decreasing Seq
          $_ ..  *    # Range

      )».first(*.is-prime) # find the first prime from both the Seq and Range

    }
}

Ruby, 57 54 bytes
->n,m{[*n..m,*m..n].all?{|x|?1*x=~/^(11+)\1+$/}||n==m}

Try it online!
Uses the horrible regex primality test from my answer (which I had forgotten about until I clicked on it) to the related question Is this number a prime?. Since we have N, M ≥ 3, the check for 1 can be removed from the pattern, making the byte count less than using the built-in.
Note: The regex primality test is pathologically, hilariously inefficient. I believe it's at least O(n!), though I don't have time to figure it right now. It took twelve seconds for it to check 100,001, and was grinding for five or ten minutes on 1,000,001 before I canceled it. Use/abuse at your own risk.

At that rate it is likely n². You know, 100001! = 2824257650254427477772164512240315763832679701040485762827423875723843380680572028502730496931545301922349718873479336571104510933085749261906300669827923360329777024436472705878118321875571799283167659071802605510878659379955675120386166847407407122463765792082065493877636247683663198828626954833262077780844919163487776145463353109634071852657157707925315037717734498612061347682956332369235999129371094504360348686870713719732258380465223614176068 ... (Warning: The output exceeded 128 KiB and was truncated.) which will take millenia to run.

Retina, 58 bytes
\b(.+)¶\1\b

.+
$*
O`
+`\b(1+)¶11\1
$1¶1$&
A`^(11+)\1+$
^$

Try it online! Explanation:
\b(.+)¶\1\b

If both inputs are the same, simply delete everything, and fall through to output 1 at the end.
.+
$*

Convert to unary.
O`

Sort into order.
+`\b(1+)¶11\1
$1¶1$&

Expand to a range of all the numbers.
A`^(11+)\1+$

Delete all composite numbers.
^$

If there are no numbers left, output 1, otherwise 0.

Python 2, 87 86 bytes
lambda*v:v[0]==v[1]or{1}-{all(v%i for i in range(2,v))for v in range(min(v),max(v)+1)}

Try it online!

I like your set usage, even though it is not required for 87 bytes.

@JonathanFrech I got it to 86 using sets

C (gcc), 103 bytes 100 bytes
i,j,p,s;f(m,n){s=1;for(i=m>n?i=n,n=m,m=i:m;i<=n;i++,p?s=m==n:0)for(p=j=2;j<i;)p=i%j++?p:0;return s;}

Try it online!

Jelly, 6 bytes
ÆpżÆnE

Try it online!
-2 thanks to Dennis.

APL (Dyalog Unicode), 18+16 = 34 24 bytes
⎕CY'dfns'
∧/=/4 ¯4∘.pco⎕

Try it online!
Thanks to Adám for 10 bytes.
The line ⎕CY'dfns' (COPY) is needed to import the dfns (dynamic functions) collection, included with default Dyalog APL installs.
How it works:
∧/=/4 ¯4∘.pco⎕ ⍝ Main function. This is a tradfn body.
             ⎕ ⍝ The 'quad' takes the input (in this case, 2 integers separated by a comma.
          pco  ⍝ The 'p-colon' function, based on p: in J. Used to work with primes.
    4 ¯4∘.     ⍝ Applies 4pco (first prime greater than) and ¯4pco (first prime smaller than) to each argument.
  =/           ⍝ Compares the two items on each row
∧/             ⍝ Applies the logical AND between the results.
               ⍝ This yields 1 iff the prime clusters are equal.

Haskell, 81 bytes
A straightforward solution:

p z=[x|x<-z,all((0/=).mod x)[2..x-1]]!!0
c x=(p[x-1,x-2..],p[x+1..])
x!y=c x==c y

Try it online!

J, 15 bytes
-:&(_4&p:,4&p:)

How it works:
   &(           ) - applies the verb in the brackets to both arguments
            4&p:  - The smallest prime larger than y
      _4&p:       - The largest prime smaller than y
           ,      - append
 -:               - matches the pairs of the primes

Try it online!

Mathematica, 39 27 26 bytes
Equal@@#~NextPrime~{-1,1}&

Expanded:
                         &  # pure function, takes 2-member list as input
       #~NextPrime~{-1,1}   # infix version of NextPrime[#,{-1,1}], which
                            # finds the upper and lower bounds of each
                              argument's prime clusters
Equal@@                     # are those bounds pairs equal?

Usage:
Equal@@#~NextPrime~{-1,1}& [{8, 10}]
(*  True  *)

Equal@@#~NextPrime~{-1,1}& [{6, 8}]
(*  False  *)

Equal@@#~NextPrime~{-1,1}& /@ {{8, 10}, {20, 22}, {65, 65},
    {73, 73}, {86, 84}, {326, 318}, {513, 518}}
(*  {True, True, True, True, True, True, True}  *)

Equal@@#~NextPrime~{-1,1}& /@ {{4, 5}, {6, 8}, {409, 401},
    {348, 347}, {419, 418}, {311, 313}}
(*  {False, False, False, False, False, False}  *)

Contributions: -12 bytes by Jenny_mathy, -1 byte by Martin Ender

This only checks next prime. Try NextPrime[#,{-1,1}]

@Jenny_mathy : I see you are correct.  Caught by the "348, 347" test case, which is now demonstrated to pass.

27 bytes: Equal@@NextPrime[#,{-1,1}]& takes as input [{N,M}] or if you want to keep the original input use this 30 bytes: Equal@@NextPrime[{##},{-1,1}]&

@Jenny_mathy : Well, ..., the specified input is two integers, not a list, so ...

@EricTowers taking a list is fine. Also, you can save a byte by using infix notation #~NextPrime~{-1,1}.

Stax, 9 bytes
α╖ª»º√π├╔

Run and debug it

05AB1E, 3 bytes
ŸpË

Port of @ETHproductions's Jelly answer, so make sure to upvote him!
Try it online or verify all test cases.
Explanation:
Ÿ    # Create an inclusive ranged list of the (implicit) input-pair
 p   # Check for each value in the list whether it's a prime (1 if truthy; 0 if falsey)
  Ë  # Check if all values are the same (so either all truthy or all falsey)
     # (after which the result is output implicitly)

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/


text:
Seqindignot sequence
Title is made up, from 'Sequence Index Digit Not'.
Challenge:
Given an integer n which is >= 0, output the n'th number of the following sequence.
Here are the first 50 items, with it's (0-indexed) index above it:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
1 0 3 2 5 4 7 6 9 8 22 20 30 24 23 26 25 28 27 32 11 33 10 14 13 16 15 18 17 31 12 29 19 21 50 40 41 42 44 45 35 36 37 51 38 39 52 53 55 56 34

How does this sequence work?
The number at index n must be the first in order that does not have any digits in common with n, and hasn't occurred yet for previous indexes. So when we look at normal sequence like this from 0-60:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60

We define the n'th values like this:

0: The first number (0) contains the same digit, so we look for the next (1), which does not contain the same digit. So n=0 outputs 1.
1: The first number (0) does not contain the same digit, so n=1 outputs 0.
2: We've already encountered 0 and 1, and the next digit (2) contains the same digit, so we look for the next (3), which does not contain the same digit. So n=2 outputs 3.
...
10: We've already encountered 0-9, so the next in line is 10. 10-19 contain the matching digit 1, 20 contains the matching digit 0, 21 contains the matching digit 1 again, 22 is valid, so n=10 outputs 22.
etc.

Challenge rules:

If your language is 1-indexed (or you choose to) you are allowed to start the sequence at 3 2 5 4 7 ... (skipping the 1 at n=0 and the 0 at n=1).
The minimum largest index you should support is 25,000. NOTE: The sequence stops at index 1,023,456,788, because the next index in line contains all 10 digits.
You are also allowed to output / return an array/list of the entire sequence up to and including index n if you want to.

General rules:

This is code-golf, so shortest answer in bytes wins.
Don't let code-golf languages discourage you from posting answers with non-codegolfing languages. Try to come up with an as short as possible answer for 'any' programming language.
Standard rules apply for your answer, so you are allowed to use STDIN/STDOUT, functions/method with the proper parameters and return-type, full programs. Your call.
Default Loopholes are forbidden.
If possible, please add a link with a test for your code.
Also, please add an explanation if necessary.

Test cases:
This sequence actually created pairs regarding index and outputs. If index n outputs o, index o outputs n. So you can input either the left or right, and the output will be the other side:
0      <->  1       (this test case is optional)
2      <->  3
10     <->  22
12     <->  30
34     <->  50
89     <->  100
111    <->  200
112    <->  300
199    <->  322
2231   <->  4456
9605   <->  11118
19235  <->  46000
23451  <->  60668
25000  <->  13674

Here is a pastebin of the first 25,001 test cases if you want to try others.

Related, but not a dupe.

As with the related challenge, the scatterplot is quite fun. :)

@MartinEnder When I saw the scatterplot of the related challenge, I indeed figured this one would be similar. Turns out it indeed is rather similar, but still different. :)

How come such an important sequence is not on OEIS?

@StewieGriffin Good question. Actually, I think all my sequence-challenges so far weren't in OEIS (yet) when I posted them. ;)

My answer will stack overflow n > 71. Is that a problem?

@Neil Sorry, but "The minimum largest index you should support is 25,000." I don't mind slightly lower (like > 5k), but 71 is a bit too low. I'm afraid you'll have to find a different approach.. :(

Either that or find an interpreter that supports tail recursion...

I don't get the "1-based index" option, wouldn't the sequence go [2,1,4,3,6,5,8,7,10,9,20,30,22,23,...]? (i.e. index starting at 1 and each term is the first with no colliding digits and not yet used >=1)

Pyth, 18 bytes
u+Gf!|}TG@`H`T0hQY

Try it here! or Check more test cases!
Note that this returns the entire sequence up to index N, but the link returns the last number only, by prepending an e (end). If you want to see the raw value returned by this program, just remove it.
How it works

u+Gf!|}TG@`H`T0hQY  - Full program.

u     ...      hQY  - Reduce hQ (the input incremented) from left to right, with the
                       function ...(G, H), with starting value Y (the empty list).
                       G is the current value and H is the iteration index.
   f          0     - First integer starting from 0, that satisfies the following:
      }TG             - Appears in G...
     |   @`H`T        - Or its (string) intersection with the current index (H) is
                        non-empty.
    !                 - Logical NOT (boolean negation).
 +G                 - Append the value obtained above to the current value (G).
                      This becomes the given value for the next iteration.
                    - Implicitly print all intermediate results, or add e to print
                      the last one.

Python 2, 92 91 89 88 bytes
a=()
i=0
exec"x=0\nwhile set(`x`)&set(`i`)or x in a:x+=1\na+=x,;i+=1;"*-~input()
print a

Try it online!
Prints a list of the first n+1 numbers

Different approach, which is a lot faster:
Python 2, 96 bytes
n=input()
r=range(9*n)
i=0
exec"x=0\nwhile set(`r[x]`)&set(`i`):x+=1\nprint r.pop(x),;i+=1;"*-~n

Try it online!

88 bytes using a tuple

Haskell, 80 69 bytes
f n=[x|x<-[0..],all(`notElem`show n)$show x,all(/=x)$f<$>[0..n-1]]!!0

Try it online!
Very slow for large n.
f n=
    [x|x<-[0..]     ] !!0          -- pick the first of all 'x' from [0..]
                                   -- where
      all(`notElem`show n)$show x  -- no digit of 'n' appears in 'x', and
      all(/=x)                     -- 'x' is not seen before, i.e. not in the list
               f<$>[0..n-1]        -- 'f' mapped to [0..n-1]

Edit: @Laikoni saved 10 bytes. Thanks!

Computing the nth term directly instead of indexing into the sequence is shorter: Try it online!

Java (OpenJDK 8), 218 217 213 210 202 200 172 171 170 168 167 bytes
I cannot believe that I didn't just return k all this time...
i->{int j=-1,k=0,y=1;for(String r=" ",e=r;j++0;k++)for(int f:(k+(y=0)+"").getBytes())y+=(e+j).indexOf(f)<0&!r.contains(e+k+e)?0:1;return~-k;}

Try it online!

Hmm, that's quite a different approach then I was using when I made the pastebin with my Java program. And it seems you can golf for(char f:(""+k).toCharArray()) to for(int f:(""+k).getBytes()), r.substring(-~r.trim().lastIndexOf(32)); and to r.substring(r.lastIndexOf(32)-1).

Must be trimmed before lastIndexOf as there's a space on the end

Ah, I indeed made a mistake.. I knew the String contained both a leading and trailing space, but my incorrectly suggested change only works for the first 10 single-digit numbers.. My bad

APL (Dyalog), 39 bytes
0∘{0=⍵:1⋄(~⍺∊0∇¨⍳⍵)∧⊃∧/≠/⍕¨⍺⍵:⍺⋄⍵∇⍨⍺+1}

Uses ⎕IO←0.
Try it online!
How?
Recursion.
0=⍵:1 - take a guess.
~⍺∊0∇¨⍳⍵ - left arg (accumulator) is not already in previous results
∧⊃∧/≠/⍕¨⍺⍵ - and the string representation of the accumulator and n are different
:⍺ - then return the accumulator.
⍵∇⍨⍺+1 - otherwise, increment accumulator and recurse.

Wow.. I know the default rule is "given any amount of memory and time", but your code already times out for n=10 in TIO.. :S That must be a very performance-heavy operation you're doing there. Is it the recursion that causes this, or is something else the bottleneck?

@KevinCruijssen the second condition basically apply the function on the range of 0..n-1, and considering the same apply for every call, that would come roughly at a huge O(2^n). of course it would be lower with a more reasonable code, but that's where the bottleneck sits

Python 3, 92 bytes
o=1,
for i in range(int(input())):
 x=0
 while{*str(x),x}&{*str(~i),*o}:x+=1
 o+=x,
print(o)

Try it online!
This prints all the terms up to the Nth one. Thanks to Dennis for  -4  -5 bytes!

JavaScript (ES6), 103 88 81
Edit Revised including many clever ideas by @Neil
n=>eval("for(r=[j=i=0];i<=n;)j=r[j]||(i+'').match(`[${j}]`)?j+1:!(r[k=j]=++i);k")

Starting point
Basic idea: a loop from 0 to n, and an inner loop checking values still not used
n=>{
  var r=[]
  for(i=0;i<=n;i++)
  {
    s=new Set(i+'')
    for(j=-1;s;)
    {
      if (!r[++j] && ![...j+''].some(d=>s.has(d)))
      {
        r[j]=1
        console.log(i,j)
        s=0
      }
    }
  }
  return j
}

Current version more readable
n=>{
  for(r = [j=i=0]; i <= n; )
    if (r[j] || (i+'').match(`[${j}]`))
      ++j
    else
      r [k=j] = ++i,
      j = 0;
  return k
}

Test

var f=
n=>eval("for(r=[j=i=0];i<=n;)j=r[j]||(i+'').match(`[${j}]`)?j+1:!(r[k=j]=++i);k")

update=_=>{
  var i=+I.value
  if (i < 1e4 || confirm("Really?")) {
    O.textContent=i + ' -> ...'
    setTimeout(_=>O.textContent=i + ' -> ' + f(i), 100)
  }
}

update()
<input id=I value=100 type=number max=1023456788>
<button onclick='update()'>Go</button>
(slow when input > 1000)

Would replacing ~s.search(d) with s.match(d) work?

I think you can save another byte by changing 0 to j++, removing the ++ from the j it was on before and then starting j from 0 instead of -1.

I think I was able to switch to a single loop: n=>eval("for(r=[j=i='0'];i<=n;)r[j]|[...''+j].some(d=>i.match(d))?j++:(i=++i+'',r[k=j]=1,j=0);k")

@Neil a single loop would be wonderful

@Neil the single loop is great, thanks

Oh, you took my match idea and ran with it, very nice!

I think n=>eval("for(r=[],j=i='0';i<=n;)j=r[j]||i.match(`[${j}]`)?++j:!(i=r[k=j]=++i+'');k") saves another byte though.

@Neil thanks again, found a way to save 7

Oh, well if you're going to use numeric values for r[] then you can switch from || to | right?

@Neil problems with the return value from match that is an array (sorry can't go in chat from here)

Oh, I forgot I changed it already ;-)

Go, 217 205 bytes
package g;import("fmt";"strconv";"strings");var(
d=make(map[int]int)
a=strconv.Itoa)
func G(L int){k,i:=0,0;for;i<=L;i++{s:=a(i);k=0;for d[k]>0||strings.ContainsAny(a(k),s){k++;}
d[k]=1;}
fmt.Print(a(k));}

Alternate version (program instead of a package): Try it online!
Improvements:

removed space after outer for by using multiple assignment for i,k
importing "fmt"; + fmt.Print is shorter than os.Stdout.WriteString (holdover from package main when os.Args was needed)

Nice, your answer is the first that doesn't time out after 1 minute when I try the 25000 test case. :) So not only a valid solution, but with relatively good performance as well. +1 from me! (PS: In your TIO-link it's the argument you use, input can be removed / is not used.)

Octave, 114 bytes
N=input("");o=[1];for i=1:N;j=0;while(any(o==j)||nnz(ismember(int2str(i),int2str(j))));j++;end;o=[o,j];end;[0:N;o]

Try it online!
Thanks to Kevin Cruijssen and Dlosc for the character comparison golfing.
Ungolfed
N=input("");o=[1];

for i=1:N;
    j=0;
    while(any(o==j)||nnz(ismember(int2str(i),int2str(j))));
        j++;
    end;
    o=[o,j];
end;
[0:N;o]

Basic explanation:

Outer loop and inner loop, one for index i, and another for value to add j
For each i, continue to increment j if either of the following are met:

Any j has been used before
This one gets fun. First, split each numeric value into a vector of digits (e.g., 10 becomes [1 0]) using int2str.
Then, compare the two numbers using ismember(e.g., [1 0] and [2 1] would return [1 0]) and then nnz to see if any columns matched.

If none of the above are met, you have the next number! Append to o, the output matrix
Print original indices with output matrix

Nice answer, +1 from me. And seems @DLosc is right, it works even without both -'0'. But if there is some edge case we both haven't thought of, -48 would be a shorter alternative. Also, both sprintf('%d',...) can be int2str(...).

Pip, 30 bytes
29 bytes of code, +1 for -p flag.
Fn,a+1{Y0WyNl|_NyMSn++ylPBy}l

Try it online!
Outputs the whole list. Warning: highly inefficient; the 2231 input case has been running for 35+ minutes on my laptop and still hasn't finished.
Explanation
                               a is cmdline arg, l is [] (implicit)
Fn,a+1{                    }   For each n in range(a+1):
       Y0                       Yank 0 into y
         W                      While...
          yNl|                  y is in l, or...
              _Ny               lambda function: arg is in y
                 MSn            mapped to digits of n and result list summed
                                (i.e., any digit of n is in y):
                    ++y          Increment y
                       lPBy     Once we have a y that meets the criteria, push it to
                                the back of l
                            l  Output l (formatted with -p flag)

Perl 5, 60 bytes
59 bytes code + 1 for -p.
$_="@{[0..($;=++$_)*9]}";$_=eval's/\b[^ $-]+ //;$-++;$&;'x$

Try it online! (Includes -l for visual purposes and $-=0; to reset each iteration)

Jelly, 20 bytes
Pyth beats Jelly. Go Mr. Xcoder!
Df⁹LD¤ȯeṆ
0ç1#ɓ;
1Ç¡

A full program taking input from STDIN and outputting in the list format option using Jelly's list representation*. Uses the standard 0 based indexing.
* single element lists have no surrounding [], so 0 outputs 1, while 1 outputs [1, 0] etc.
Try it online!
How?
Df⁹LD¤ȯeṆ - Link 1, can append n to current? n, number; current, list
D         - convert n to decimal list
     ¤    - nilad followed by link(s) as a nilad:
  ⁹       -   chain's right argument, current
   L      -   length
    D     -   convert to a decimal list
 f        - filter discard from left if not in right
       e  - n exists in current?
      ȯ   - left logical OR right (empty lists are falsey)
        Ṇ - logical NOT

0ç1#ɓ; - Link 2, append next number: current, List
   #   - n find (count up finding first n matches):
  1    - ...finding: 1 match
0      - ...stating at: n=0
 ç     - ...doing: the last link as a dyad (left=n, right=current)
    ɓ  - new swapped-arg-dyadic chain (left = current, right = list of the found n)
     ; - concatenate

1Ç¡ - Main link: no arguments
1   - initialise the return value to 1
  ¡ - repeat input() times:
 Ç  -   last link (2) as a monad
    - implicit print

Visual Basic .NET (.NET 4.5), 260 259 bytes
-1 byte thanks to Kevin Cruijssen
Function A(n)
Dim p=New System.Collections.Generic.List(Of Long),j="0",g=0
For i=0To n
j=0
While 1
If Not p.Contains(j)Then
g=1
For Each c In i.ToString
If j.Contains(c)Then g=0
Next
If g Then Exit While
End If
j+=1
End While
p.Add(j)
Next
A=p(n)
End Function

Loops through, generating previous terms in the sequence to then compare later. Then iterates the number as a string looking for matches.
Abuses VB.NET's typing system. For example, j is a string, but adding one converts to an integer for me. Integers are converted to Booleans where 0 is False and the rest are True.
Try it online!

I never programmed in Visual Basic, but it seems you can remove the space at If Not p.Contains(j)Then same like you did at If j.Contains(c)Then g=0 below. Also, If Not p.Contains(j)Then \n g=1 \n For Each c In i.ToString \n If j.Contains(c)Then g=0 \n Next \n If g Then Exit While \n End If can be shortened by removing g and using Exit While directly in the for-loop: If Not p.Contains(j)Then \n For Each c In i.ToString \n If j.Contains(c)Then Exit While \n Next \n End If, which will become 241 bytes by the looks of it.

@KevinCruijssen Definitely can remove the space to make it Contains(c)Then, I just missed it. I like what you're thinking, but I'm using g as a sentinel to see if the string contains the number or not. Your link gives the wrong answers, but I'll see if I can rework some of the inner logic along what you're thinking.

Ah oops.. It indeed fails.. Now it's only outputting the input. My bad. Shouldn't make these comments when it's evening and I'm tired from work. ;)


text:
Carve a square from a string
Your challenge today is to take a multiline string, and output the biggest square contained within the string that includes the top left corner.
A square string is one where:

Each line has the same number of characters
The number of characters on each line is equal to the number of lines.

Consider the following possible input string:
abcde
fgh
asdf
foobar

The largest square you can take from it that includes the first character (the a in the topleft corner) is this:
abc
fgh
asd

There can't be a square of side-length 4, because the second line isn't long enough. Now consider this potential input:
a
bcd
edf
ghi

The biggest square here is just a. The 3x3 square formed in the bottom doesn't contain the very first character, and doesn't count.
Here's a few more test cases:
a

a

abc
def
gh

ab
de

ab
cd

ab
cd

abcde
fghij
klm
no

abc
fgh
klm

a
b

a

You may require input to be delimited by your choice of LF, CR, or CRLF.
The newline character(s) are not considered part of the line's length.
You may require there to be or to not be a trailing newline in input, which doesn't count as an additional line.
Input is a string or 1D char array; it is not a list of strings.
You may assume input is non-empty and all lines are non-empty, and that it only contains printable ASCII, including spaces and newlines (for the line delimiter) but not tabs.
This is code-golf, fewest bytes wins!

related

+1 for an interesting challenge, -1 for strict I/O

@Dennis not every solution needs to use .split('\n') so I don't see why some should get it for free.

It's not (just) about having to add bytes for boring boilerplate. Some approaches (e.g., recursive functions) become completely impractical if there's pre- or postprocessing.

@Dennis I hadn't thought about it like that. Do you think I should change it now, or is it too late?

Not sure. I think it would improve the challenge, but asking Asking 15 users to rethink their approaches...

@Pavel I think definitely too late, there's too many answers.

Brachylog, 11 bytes
ṇ⊇ᵐẹa₀ṁcᵐ~ṇ

Try it online!
Explanation
ṇ             Split on linebreaks
 ⊇ᵐ           Take a subset of each line
   ẹ          Split the lines into list of chars
    a₀        Take a prefix of this list of lists of chars
      ṁ       It is a square matrix
       cᵐ     Concatenate the list of chars back into strings
         ~ṇ   Join the strings with linebreaks

Good job on the shortest solution (so far), Brachylog sure likes squares, doesn't it?

@Pavel The ṁ built-in is indeed quite handy!

Husk, 13 bytes
►oΛ≈S+TzṀ↑Nḣ¶

Try it online!
Explanation
►oΛ≈S+TzṀ↑Nḣ¶  Implicit input, say "ab\nc".
            ¶  Split at newlines: ["ab","c"]
           ḣ   Take prefixes: [["ab"],["ab","c"]]
       z  N    Zip with [1,2,3..
        Ṁ↑     by taking that many characters from each row: [["a"],["ab","c"]]
►o             Find rightmost element that satisfies this:
  Λ            all strings in
    S+T        the list concatenated to its transpose
   ≈           have the same length: ["a"]
               Implicitly print separated by newlines.

How is this even a programming language - you've just pasted some obscure unicode characters! ;)

@Petar Welcome to the world of golfing languages, which are designed specifically to use as few bytes as possible to do a certain task. Part of this is to have a custom code page, so that there is a character for each possible byte, instead of the usual 95 printable ASCII. But don't worry, there are also much more legible golfing languages; for example my MATL entry [/shameless self-promotion]

GNU sed, 106 + 1 94 + 2 = 96 bytes
+2 bytes for -rz flags. Uses unprintable characters NUL and BEL, shown as @ and # here. See below for an xxd dump.
Thanks to @seshoumara for sending me down the path to -z.
s/^/@/gm
s/.*/#&\n/
:B
s/@(.)/\1@/mg
s/#(.+\n)/\1#/m
/#.*@./M!b
/@\n.*#/!bB
:
s/@[^\n]*|#.*//g

Try it online!
Explanation
This works by inserting two cursors into the text—one to step over lines and one to step over columns. The cursors are represented by NUL (0x00) and BEL (0x07), respectively, but in the below examples I'll use @ and #. Suppose we have this input:
abcde
fgh
asdf
foobar

The BEL cursor is inserted before the 0th column and the BEL cursor before the 0th line (here I've kept the columns aligned for legibility; but in actuality there is no left padding):
#@abcde
 @fgh
 @asdf
 @foobar

In a loop, the cursors are moved one character to the right and one line down, respectively:
 a@bcde
#f@gh
 a@sdf
 f@oobar

 ab@cde
 fg@h
#as@df
 fo@obar

 abc@de
 fgh@
 asd@f
#foo@bar

After each iteration, it checks two conditions:

On the line with the line cursor, is there a column cursor and can the column cursor move to the right?
On the lines before the line cursor, can every column cursor move to the right?

If either condition is false, the loop ends. The script finishes by deleting everything after @ on each line and everything after # in the pattern space.
xxd dump
00000000: 732f 5e2f 002f 676d 0a73 2f2e 2a2f 0726  s/^/./gm.s/.*/.&
00000010: 5c6e 2f0a 3a42 0a73 2f00 282e 292f 5c31  \n/.:B.s/.(.)/\1
00000020: 002f 6d67 0a73 2f07 282e 2b5c 6e29 2f5c  ./mg.s/.(.+\n)/\
00000030: 3107 2f6d 0a2f 072e 2a00 2e2f 4d21 620a  1./m./..*../M!b.
00000040: 2f00 5c6e 2e2a 072f 2162 420a 3a0a 732f  /.\n.*./!bB.:.s/
00000050: 005b 5e5c 6e5d 2a7c 072e 2a2f 2f67       .[^\n]*|..*//g

You can remove the first loop, A, because the statement says you have to read the input as a string, so you can receive "line1\nline2\nline3" etc. Other answers did this too. That should get the count below 100 :)

@seshoumara Other answers do line1\nline2\nline3 where \n is \x5C\x6E? Which?

Can you give me a link? (Click on "share" at the bottom of any answer.) Or show me in a TiO what you mean? In all of the Python and PHP answers I see \n is interpreted as a newline character (\x0A, not \x5C\x6E) and I can't find a way to make sed take input with newline characters as a single line.

@seshoumara Hah, nevermind, I just remembered the -z flag. Thanks!

Python 2, 81 bytes
l=input().split('\n')
i=0
while zip(*l[:i+1])[i:]:i+=1
for x in l[:i]:print x[:i]

Try it online!

An interesting method, but 2 bytes longer.
Python 2, 83 bytes
l=input().split('\n')
while len(zip(*l))<len(l):l.pop()
for x in l:print x[:len(l)]

Try it online!

Doesn't input only read one line?

@Pavel, if you look at the online example, you can see it is using explicit newline characters to keep the input a one-line string. Probably opting for this method because raw_input() would add more bytes.

JavaScript (ES6), 77 bytes
f=(s,i=1,m=s.match(`^${`(.{${i}}).*
`.repeat(i)}`))=>m?f(s,i+1)||m.slice(1):0

Recursively uses a regular expression to search for a larger and larger square until none is found.
The regular expression would be this for a 3x3 square:
^(.{3}).*
(.{3}).*
(.{3}).*

Input is expected to end with a newline, and output is a list.
Explanation:
f = (s,                                            //input
     i = 1,                                        //start searching for a 1x1 square
     m = s.match(`^${`(.{${i}}).*\n`.repeat(i)}`)  //match on the regex
    )=>
    m ? f(s, i+1)                   //if there's a match, recurse on the next-sized square
        || m.slice(1) :             //if there's not a next-sized square, return the match
        0                           //no match for this square, so stop recursing

Snippet:

f=(s,i=1,m=s.match(`^${`(.{${i}}).*
`.repeat(i)}`))=>m?f(s,i+1)||m.slice(1):0

console.log(f(`abcde\nfgh\nasdf\nfoobar`));
console.log(f(`a\nbcd\nedf\nghi\n`));
console.log(f(`a\n`));
console.log(f(`abc\ndef\ngh\n`));
console.log(f(`ab\ncd\n`));
console.log(f('abcde\nfghij\nklm\nno'));
console.log(f(`a\nb\n`));

Brachylog, 16 bytes
ṇ{ẹa₀ᵐa₀ṁ}ᶠtcᵐ~ṇ

Try it online!

Explanation, please?

R, 84 83 81 76 bytes
-5 bytes porting Dennis' approach with sum

cat(substr(x<-readLines(),1,m<-sum(cummin(nchar(x))>=seq(x)))[1:m],sep='\n')

Try it online!
reads from stdin, prints to stdout without a trailing newline.
Slightly ungolfed:
x <- readLines()                    # read in input one line at a time;
                                    # saved as a vector of strings
minChar <- cummin(nchar(x))         # rolling minimum of all line lengths
lineNum <- seq(x)                   # line number
mins <- minChar>=lineNum            # the min between the line number and the line lengths
m <- sum(mins)                      # the sum of those is the size of the square
cat(substr(x,1,m)[1:m],sep='\n')    # print the first m characters of the first m lines,
                                    # and join with newlines

C (gcc), 162 159 151 147 144 142 137 bytes
There must be some strokes to golf away here...
i,l=9;char*p,s[9][8];main(t){for(p=s;~(*p=getchar());)p=*p<32?*p=0,l=(t=strlen(s+i))<l?t:l,s[++i]:p+1;for(i=0;i<l;puts(s+i++))s[i][l]=0;}

Try it online!

Can !=-1 be >-1 or does getchar() output values smaller than minus one? Could it even be +1?

Potential 158 bytes.

@JonathanFrech I can use ~ to detect minus one.

@RickHitchcock Seems to work in the latest golf version.

Suggest read(0,p,1) instead of ~(*p=getchar())

Perl 5, 84 bytes
chomp(@a=<>);map$.&&=y///c>$i,@a[0..$i]while$.&&$i++<$#a;say/(.{$i})/ for@a[0..$i-1]

Try it online!
Fulfills the "abcde\nfghij\nklm\nno" test case.

you could use chop instead of chomp and ++$i<@a instead of $i++<$#a

Java 8, 150 bytes
s->{String q[]=s.split("\n"),r="";int l=q[0].length(),i=0,t;for(;i<l;l=t<l?t:l)t=q[i++].length();for(i=0;i<l;)r+=q[i++].substring(0,l)+"\n";return r;}

Explanation:
Try it here.
s->{                          // Method with String as both parameter and return-type
  String q[]=s.split("\n"),   //  Split the input on new-lines, and put it in an array
         r="";                //  Result-String, starting empty
  int l=q[0].length(),        //  Length of the lines, starting at the length of line 1
      i=0,                    //  Index-integer, starting at 0
      t;                      //  Temp integer
  for(;i<l;                   //  Loop (1) from 0 to `l` (exclusive)
      l=t<l?                  //    After every iteration: if `t` is smaller than `l`:
         t                    //     Change `l` to `t`
        :                     //    Else:
         l)                   //     Leave `l` the same
    t=q[i++].length();        //   Set `t` to the length of the current line
                              //  End of loop (1) (implicit / single-line body)
  for(i=0;i<l;                //  Loop (2) from 0 to `l` (the determined square dimension)
    r+=                       //   Append the result-String with:
       q[i++].substring(0,l)  //    The current row chopped at `l-1`
       +"\n"                  //    + a new-line
  );                          //  End of loop (2)
  return r;                   //  Return the result-String
}                             // End of method

Jelly, 15 bytes
L€«\‘>Jx@Z
ỴÇÇY

Try it online!
How it works
ỴÇÇY        Main link. Argument: s (string)

Ỵ           Split s at linefeeds, yielding a string array.
 Ç          Apply the helper link.
  Ç         Apply the helper link again.
   Y        Join, separating by linefeeds.

L€«\‘>Jx@Z  Helper link. Argument: A (string array/2D character array)

L€          Compute the length of each row/line.
  «\        Take the cumulative minimum.
    ‘       Increment each minimum.
      J     Indices; yield [1, ..., len(A)].
     >      Perform elementwise comparison. If the output should have n lines, this
            yields an array of n ones and len(A)-n zeroes.
         Z  Zip/transpose A.
       x@   For each string t in the result to the right, repeat its characters as
            many times as indicated in the result to the left, discarding all but
            the first n characters.

MATL, 33 bytes
10-~ft1)wdhqY<tn:vX<X>:GYbowt3$)c

Try it online!
My spidey sense tells me that there's probably a shorter way (I'm thinking something with Ybo right from the start)... Requires a newline at the end. (Note: I over-engineered this a bit, as this will handle empty lines as well, which is not required. I'll see if I can reduce the bytecount, because in code golf, it's not a feature, but a bug)

@Pavel Guiseppe was referring to another version, which I rolled back because it indeed had a bug.

APL (Dyalog), 25 bytes*
Tacit prefix function. Returns a matrix.
(↑↑⍨2⍴(⌊/≢,≢¨))⎕AV[3]∘≠⊆⊢

Try it online!
It is really an atop of two independent functions, namely ⎕AV[3]∘≠⊆⊢ which deals with the awkward input format and ↑↑⍨2⍴(⌊/≢,≢¨) which does the actual interesting work.
⎕AV[3]∘≠ difference from LF (the third element of the Atomic Vector – the character set)
⊆ partitions (substrings beginning at values larger than their predecessor and  drop at 0s)
⊢ the argument
(…) apply the following tacit function:
 2⍴(…) reshape the following to length 2:
  ⌊/ the minimum of
  ≢ the number of strings
  , followed by
  ≢¨ the number of characters in each string
↑⍨ take that many rows and columns from
 ↑ the strings mixed together to form a matrix (padding with spaces)

* In Classic with ⎕ML (Migration Level) 3 (default on many systems) and substituting ⊂ for ⊆ and ⊃ for the leftmost ↑. Tio!

If it's the same length in Dyalog Classic you might as well say it's Dyalog Classic and not use the footnote.

@Pavel Both Classic and ⎕ML←3 are deprecated, so I'd rather show the language as it would normally appear. In fact, almost all my Dyalog APL solutions assume Classic just because we count bytes instead of characters, though even the Unicode version assigns meaning to less than 256 characters.

Haskell, 92 88 bytes
unlines.f.lines
f s|let t=take$until(all.(.l).(<=)<*>(`take`s))pred$l s=t<$>t s
l=length

Try it online!

Perl 5, 60 +5 (-0777p) bytes
$.++while/^(.{$.}.*
){$.}/;$_=join"
",(/.{$.}/gm)[0..--$.-1]

Try it online

The last line of input must end with a newline in case it belongs to output.
In case of two consecutive newlines -00 may option be changed by -0777.

Two consecutive newlines is possible, so you'll need -0777. What do -00 and -0777 do, anyway.

-0 is to specify the record separator in octal format 777 is a special value to indicate no separator so the whole file is read, 0 is another special value to indicate "paragraph mode", separator is more than 1 consecutive newlines

Perl 6, 158 140 bytes
my$c;for ^(my@b=lines).elems {any(@b.head(++$c).map({.substr(0,$c).chars <$c}))&&$c--&&last;};say @b.head($c).map({.substr(0,$c)}).join("
")

Try it online!
Hooray for my first Perl 6 answer. I'll play around with some command line options to see if I can golf this a bit more. All help saving bytes is welcome!

Python 2, 132 bytes
def f(s):s=s.split("\n");return["\n".join([l[:j+1]for l in s[:j+1]])for j,v in enumerate(s[0])if all(len(l)>j for l in s[:j+1])][-1]

Try it online!

Python 2, 103 bytes
def f(i):
 i=i.split('\n');x=0
 while all(v[x:]for v in i[:x+1])*i[x:]:x+=1
 for v in i[:x]:print v[:x]

Try it online!

JavaScript (ES6), 95 bytes

f=
s=>(g=s=>s.slice(0,a.findIndex((e,i)=>a.some((s,j)=>j<=i&!s[i]))))(a=s.split`
`).map(g).join`
`
<textarea oninput=o.textContent=f(this.value+`\n`)></textarea><pre id=o>

Requires a trailing newline in input.

Wolfram Language (Mathematica), 81 bytes
Column[For[i=1,d=c;MatrixQ[c=StringExtract[#,"\n"->;;i,""->2;;i+1]],i++];Row/@d]&

Try it online!

PHP, 123 bytes
for(;preg_match("#^(\S{".++$i."}.*
){"."$i}#",$s="$argv[1]
"););while($k<$i-1)echo substr(split("
",$s)[+$k++],0,$i-1),"
";

requires PHP 5.4, 5.5 or 5.6. Replace split with explode for later PHP.
Run with php -nr '<code> '<string>'
or try it online.
(Make sure you select a suiting PHP version!)

Scala, 201 bytes
type S=String
def c(s:S):S={val? =s split "\n"
var(z,q:Seq[S])=(Seq(?size,?(0).size).min,Nil)
while(1<2){?map(i=>{if(i.size>=z)q=q:+i.take(z)
if(q.size==z)return q mkString "\n"})
q=Nil;z-=1}
return""}

Try it online!
First time golfing in this language, so maybe not the greatest.


text:
Expand a number
Expand a number
Your task is to expand an integer greater than 0 in the following manner:
Split the number into decimal digits and for each digit generate a list according to these rules:

if the digit is odd, the list starts with the digit and goes down to 1;
if the digit is even, the list starts with the digit and goes up to 9.
if the digit is 0, the list is empty.

Write down the lists for the odd numbers below the digits, and above for the even ones. Then top-align the columns and collect the digits in each row to make integers. As a final step add up the numbers to find the expansion of the  number.
Here's an example of the above rules applied to 34607:
 9
 8
 79
 68
 57
346 7 ->  399 7 -> 3997 -> 9418
2   6     288 6    2886
1   5     177 5    1775
    4      66 4     664
    3      5  3      53
    2      4  2      42
    1         1       1

Here are the test cases:
1: 1
2: 44
3: 6
44: 429
217: 1270
911: 947
2345: 26114
20067: 3450
34875632: 70664504
9348765347634763: 18406119382875401

This is code-golf, so the shortest answers in bytes in each language win.

Can we take input as a string? Or as an array of digits?

@Arnauld It must be an integer, and to split it to digits with your program/function

@GalenIvanov But if input is from stdin, I suppose that's ok (even though technically a string), right?

@Adám Yes, technically it's a string, so that's ok.

And here I thought it would be an expansion like this.

@Engineer Toast Yes, something like this :)

Jelly, 13 bytes
Dḟ0RrḂ?€9UZḌS

A monadic link taking and returning positive integers.
Try it online! or see the test-suite.
How?
Dḟ0RrḂ?€9UZḌS - Link: positive integer           e.g. 702
D             - cast to a decimal list                [7,0,2]
  0           - literal zero                          0
 ḟ            - filter discard                        [7,2]
        9     - literal nine
       €      - for each:
      ?       -   if:
     Ḃ        -   ...condition: bit (modulo by 2)      1              ,0
   R          -   ...then: range ([1,...n])            [1,2,3,4,5,6,7],n/a
    r         -   ...else: inclusive range ([n,...9])  n/a            ,[2,3,4,5,6,7,8,9]
         U    - upend                                 [[7,6,5,4,3,2,1],[9,8,7,6,5,4,3,2]]
          Z   - transpose                             [[7,9],[6,8],[5,7],[4,6],[3,5],[2,4],[1,3],2]
           Ḍ  - cast from decimal lists               [79,68,57,46,35,24,13,2]
            S - sum                                   324

Perl 6,  68  66 bytes
{sum roundrobin(.comb».&{$_%2??($_...1)!!(9...+$_) if +$_})».join}

Try it
{sum roundrobin(.comb».&{[R,] $_%2??1..$_!!$_..9 if +$_})».join}

Try it
Expanded:
{  # bare block lambda with implicit parameter ｢$_｣

  sum

    roundrobin( # grab from the sub lists in a round robin fashion

      .comb\             # split the input into digits
      ».&{               # for each digit do this

        [R,]             # reduce with reversed &infix:«,» (shorter than reverse)

              $_ % 2     # is the digit not divisible by 2?
          ??  1  .. $_   # from 1 to the digit
          !!  $_ ..  9   # from the digit to 9

        if +$_           # only do the above if the current digit isn't 0
                         # (has the effect of removing 0 from the list)
     }

    )».join     # join each of the sub-lists from roundrobin
}

Japt, 18 bytes
ì f ®òZu ª9 wÃy xì

Try it online!

Java 11, 210 209 191 181 bytes
n->{long r=0;var a="0".repeat(9).split("");for(int d:(n+"").getBytes())for(int k=0,x=d-48,y=9;x>0&(k<1||(d%2<1?y-->x:x-->1));a[k++]+=d%2<1?y:x);for(var q:a)r+=new Long(q);return r;}

Ok, this took quite a while (mainly because I made a mistake at first, so had to write down each step to better understand what I did wrong). Can most likely be golfed some more.
-18 bytes thanks to @ceilingcat.
Explanation:
Try it here.
n->{                             // Method with long as both parameter and return-type
  long r=0;                      //  Result-long `r`, starting at 0
  var a="0".repeat(9).split(""); //  String array `a`, filled with nine String zeroes
  for(int d:(n+"").getBytes())   //  Cast the input to a String,
                                 //   and loop over its codepoints as integers:
    for(int k=0,                 //   Row-index `k`, starting at
        x=d-48,                  //   Temp integer `x`, set to the current digit
        y=9                      //   Temp integer `y`, set to 9
        ;                        //   Inner loop, if:
         x>0                     //     The current digit is not a 0,
          &(k<1                  //     and if this is the first iteration,
             ||(d%2<1?           //     or if the digit is even:
                 y-->x           //      And `y` is larger than the digit
                                 //      (and afterwards decrease `y` by 1 with `y--`)
                :                //     or if the digit is odd:
                 x-->1));        //      And `x` is larger than 1
                                 //      (and afterwards decrease `x` by 1 with `x--`)
      a[k++]+=                   //    Append the current row with:
                                 //    (and afterwards increase `k` by 1 with `k++`)
       d%2<1?                    //     If the digit is even:
        y                        //      Append the row with `y`
       :                         //     Else (the digit is odd):
        x);                      //      Append the row with `x`
  for(var q:a)                   //  Loop over the String rows in the array:
    r+=new Long(q);              //   Convert it to a long, and add it to the result-sum
  return r;}                     //  Return the result

APL (Dyalog), 39 bytes
Full program body. Prompts for input from STDIN. Prints result to STDOUT.
+/10⊥¨0~⍨¨↓⍉↑{2|⍵:⌽⍳⍵⋄×⍵:⌽⍵,⍵↓⍳9⋄⍬}¨⍎¨⍞

Try it online!
To display the last test case correctly, ⎕FR (Floating-point Representation) has been set to 128-bit Decimal and ⎕PP (Print Precision) has been set to 34 digits.
⍞ prompt for text input from STDIN
⍎¨ execute each (gets each digit as a number)
{…}¨ for each element, apply the following function where the argument is represented by ⍵:
 2|⍵: if odd (lit. "if" division remainder when divided by 2), then:
  ⌽ reverse
  ⍳ the ɩntegers from 1 until
  ⍵ the argument
 ⋄ else
 ×⍵: if the argument is positive (lit. "if" signum), then:
  ⌽ reverse
  ⍵ the argument
  , followed by
  ⍵ argument
  ↓ elements dropped from
  ⍳9 the the ɩntegers from 1 until 9
 ⋄ else
  ⍬ empty list
↑ mix (combine) this list of lists into a single matrix, padding with zeros on the right
⍉ transpose
↓ split this matrix into a list of lists
0~⍨¨ remove all zeros from each list
10⊥¨ convert each from base-10 to normal numbers (this collects the digits)
+/ sum the numbers

Thank you for your explanation.
Just to let you know that I discovered code golf after watching you in the APL code golf video.

JavaScript (ES6), 88 83 82 bytes
f=(n,k=0)=>k<9&&+[...n+''].map(x=>+x&&(x=x&1?x:9-k<x||9)>k?x-k:'').join``+f(n,k+1)

Note
9 - k < x || 9 saves a byte over 9 - k >= x && 9 but generates 1 instead of 0 if the inequality is verified. It would be a problem if it leaded to 1 > k, triggering the wrong path in the outer ternary. But it would mean that k = 0 and therefore 9 - k = 9, so we can't possibly have 9 - k < x at the same time.
Test cases
NB: Removed the last test case which exceeds JS number precision.

f=(n,k=0)=>k<9&&+[...n+''].map(x=>+x&&(x=x&1?x:9-k<x||9)>k?x-k:'').join``+f(n,k+1)

console.log(f(1))                // 1
console.log(f(2))                // 44
console.log(f(3))                // 6
console.log(f(44))               // 429
console.log(f(217))              // 1270
console.log(f(911))              // 947
console.log(f(2345))             // 26114
console.log(f(20067))            // 3450
console.log(f(34875632))         // 70664504

Haskell, 106 104 bytes
import Data.List
f n=sum$map read$transpose$[reverse$[[c..'9'],['1'..c]]!!mod(read[c])2|c<-show n,c>'0']

Try it online!

Pip, 28 bytes
J_MS(RV{a?a%2?\,aa,tl}Ma)ZDx

Try it online!
Explanation
                      Ma      Map this function to the digits of the 1st cmdline arg:
        a?                     If digit != 0:
          a%2?                  If digit is odd:
              \,a                Inclusive-range(digit)
                 a,t            Else (digit is even), range from digit to 10 (exclusive)
                    l          Else (digit is 0), empty list
     RV{             }         Apply reverse to the result before returning it
                              This gives us a list of lists like [9 8 7 6] or [3 2 1]
    (                   )ZDx  Zip, with a default value of empty string
J_MS                          Use map-sum to join each sublist and sum the results
                              Autoprint (implicit)

How the steps proceed with 34607 as the argument:
34607
[[1 2 3] [4 5 6 7 8 9] [6 7 8 9] [] [1 2 3 4 5 6 7]]
[[3 2 1] [9 8 7 6 5 4] [9 8 7 6] [] [7 6 5 4 3 2 1]]
[[3 9 9 "" 7] [2 8 8 "" 6] [1 7 7 "" 5] ["" 6 6 "" 4] ["" 5 "" "" 3] ["" 4 "" "" 2] ["" "" "" "" 1]]
[3997 2886 1775 664 53 42 1]
9418

R, 153 146 bytes
function(n,m=n%/%10^(nchar(n):0)%%10)sum(strtoi(apply(sapply(m[m>0],function(x)c(r<-"if"(x%%2,x:1,9:x),rep("",9-sum(r|1)))),1,paste,collapse="")))

Try it online!
Sometimes, I can't tell if I'm just garbage at golfing, or if R is.... It's definitely me, saved 7 bytes thanks to user2390246, who reminded me of another way to extract digits (that I suggested myself).
You may replace strtoi with as.double to get 18406718084351604 for the last test case (which is wrong); R only has 32-bit integers.

You can save a bit by taking n as an integer and converting to digits using one of your tricks! 146 bytes

@user2390246 you know, I tried that, but I think I was fixated on using the implicit conversion to  character->int when I called : and then used strtoi anyway!

Pyth - 23 bytes
siRT.Tm*!!d@,}9d}d1dsMz

Test Suite.

Perl 5, 120 + 1 (-a) = 121 bytes
$p=y/01357/ /r;$n=y/02468/ /r;map{$p=~s/9/ /g;$p=~s/\d/$&+1/ge;$n=~s/\d/$&-1/ge;$n=~s/0/ /g;@F=($p,@F,$n)}0..7;say for@F

Try it online!

Python 2, 131 bytes
lambda n:sum(int(''.join(`n`for n in l if n))for l in map(None,*[range(n and(n%2*n or 9),(n%2<1)*~-n,-1)for n in map(int,`n*10`)]))

Try it online!

05AB1E, 16 bytes
0KεDÈi9ŸëL]íõζJO

Try it online or verify all test cases.
Or alternatively:
0KεDÈ8*>Ÿ{R}õζJO
0Kε9Ÿ¬L‚yèR}õζJO

Explanation:
0K        # Remove all 0s from the (implicit) input-integer
  ε       #  Map each digit to:
   D      #   Duplicate the digit
    Èi    #   If it's even:
      9Ÿ  #    Pop and push a list in the range [digit, 9]
     ë    #   Else (the digit is odd):
      L   #    Pop and push a list in the range [1, digit]
  ]       # Close both the if-else statement and map
   í      # Reverse each inner ranged list
     ζ    # Zip/transpose, swapping rows and columns,
    õ     # with an empty string as filler
      J   # Join each inner list together
       O  # And sum that list
          # (after which the result is output implicitly)

Burlesque, 39 bytes
riXX:nz{J2dv{{9r@}{ro}}che!<-}m[tp)im++

Try it online!
ri      #Read as int
XX      #Return list of digits
:nz     #Filter for non-zero
{
 J2dv   #Divisible by 2?
 {
  {9r@} #Range a, 9
  {ro}  #Range 1, a
 }che!  #Run based on if divisible
 <-     #Reverse the range
}m[     #Apply to each digit
tp      #Transpose digits
)im     #Join each list into single int
++      #Sum each int