How can i Maximize the total number of contacts

Question

Suppose we have 2d array A (n by n) and string S. Each cell of array can contain at most one char. Each character of the string can assign only one cell. The two consecutive characters on the string must be positioned to the neighboring cell of the grid(horizontal or vertical NOT DIAGONAL). Pair of ’1’s that are not consecutive characters of the string but are assigned to neighboring nodes of the grid are said to be in contact. For example S=10010110. The max number of contact in this string is 2. Can someone help me. IDN how to approach this problem