Рубрики

Самая длинная четная подстрока, так что сумма первой и второй половины одинакова

Для заданной строки цифр 'str' найдите длину самой длинной подстроки 'str', чтобы длина подстроки составляла 2k цифр, а сумма левых k цифр равнялась сумме правых k цифр.

Примеры :

Input: str = "123123"
Output: 6
The complete string is of even length and sum of first and second
half digits is same

Input: str = "1538023"
Output: 4
The longest substring with same first and second half sum is "5380"

Простое решение [O (n 3 )]
Простое решение — проверить каждую подстроку четной длины. Ниже приводится реализация простого подхода.

C ++

// Простая программа на C ++ для определения длины самой длинной четной длины
// подстрока с одинаковой суммой цифр слева и справа
#include<bits/stdc++.h>

using namespace std;

  

int findLength(char *str)

{

    int n = strlen(str);

    int maxlen =0; // Инициализировать результат

  

    // Выбрать начальную точку каждой подстроки

    for (int i=0; i<n; i++)

    {

        // Выбор конечной точки подстроки четной длины

        for (int j =i+1; j<n; j += 2)

        {

            int length = j-i+1;// Находим длину текущего субстрата

  

            // Вычисляем левую и правую суммы для текущего субстрата

            int leftsum = 0, rightsum =0;

            for (int k =0; k<length/2; k++)

            {

                leftsum += (str[i+k]-'0');

                rightsum += (str[i+k+length/2]-'0');

            }

  

            // Обновить результат, если необходимо

            if (leftsum == rightsum && maxlen < length)

                    maxlen = length;

        }

    }

    return maxlen;

}

  
// Программа драйвера для проверки вышеуказанной функции

int main(void)

{

    char str[] = "1538023";

    cout << "Length of the substring is " 

         << findLength(str);

    return 0;

}

  
// Этот код добавлен
// Аканкша Рай

С

// Простая программа на C, чтобы найти длину самой длинной четной длины
// подстрока с одинаковой суммой цифр слева и справа
#include<stdio.h>
#include<string.h>

  

int findLength(char *str)

{

    int n = strlen(str);

    int maxlen =0;  // Инициализировать результат

  

    // Выбрать начальную точку каждой подстроки

    for (int i=0; i<n; i++)

    {

        // Выбор конечной точки подстроки четной длины

        for (int j =i+1; j<n; j += 2)

        {

            int length = j-i+1;// Находим длину текущего субстрата

  

            // Вычисляем левую и правую суммы для текущего субстрата

            int leftsum = 0, rightsum =0;

            for (int k =0; k<length/2; k++)

            {

                leftsum  += (str[i+k]-'0');

                rightsum += (str[i+k+length/2]-'0');

            }

  

            // Обновить результат, если необходимо

            if (leftsum == rightsum && maxlen < length)

                    maxlen = length;

        }

    }

    return maxlen;

}

  
// Программа драйвера для проверки вышеуказанной функции

int main(void)

{

    char str[] = "1538023";

    printf("Length of the substring is %d", findLength(str));

    return 0;

}

Джава

// Простая Java-программа для поиска
// длина самой длинной четной подстроки
// с одинаковой суммой цифр слева и справа

import java.io.*;

  

class GFG {

  

static int findLength(String str)

{

    int n = str.length();

    int maxlen = 0; // Инициализировать результат

  

    // Выберите начальную точку каждого

    // подстрока

    for (int i = 0; i < n; i++)

    {

        // Выберите конечную точку чётного

        // длина подстроки

        for (int j = i + 1; j < n; j += 2)

        {   

            // Находим длину текущего субстрата

            int length = j - i + 1;

  

            // Рассчитать левую и правую суммы

            // для текущего субстрата

            int leftsum = 0, rightsum = 0;

            for (int k = 0; k < length/2; k++)

            {

                leftsum += (str.charAt(i + k) - '0');

                rightsum += (str.charAt(i + k + length/2) - '0');

            }

  

            // Обновить результат, если необходимо

            if (leftsum == rightsum && maxlen < length)

                    maxlen = length;

        }

    }

    return maxlen;

}

  
// Программа драйвера для проверки вышеуказанной функции

public static void main(String[] args)

{

    String str = "1538023";

    System.out.println("Length of the substring is " 

                       + findLength(str));

}
}

  
// Этот код принадлежит Prerna Saini

python3

# Простой Python 3 на основе
# программа для определения длины
# самой длинной четной длины
# подстрока с той же суммой
Количество цифр слева и справа

  

def findLength(str):

  

    n = len(str)

    maxlen = 0 # Инициализировать результат

  

    # Выберите начальную точку

        # каждой подстроки

    for i in range(0, n):

      

        # Выберите конечную точку

                число четной подстроки

        for j in range(i+1, n, 2):

                   

                        # Найти длину текущего субстрата

            length = j - i + 1 

  

            # Расчет влево и вправо

                        # суммы для текущего субстрата

            leftsum = 0

            rightsum =0

            for k in range(0,int(length/2)):

              

                leftsum += (int(str[i+k])-int('0'))

                rightsum += (int(str[i+k+int(length/2)])-int('0'))

              

  

            # Обновить результат при необходимости

            if (leftsum == rightsum and maxlen < length):

                    maxlen = length

          

      

    return maxlen

  

  
# Драйвер программы для
# проверка над функцией

str = "1538023"

print("Length of the substring is",

       findLength(str))

  
# Этот код предоставлен
# Смита Динеш Семвал

C #

// Простая программа на C # для поиска
// длина самой длинной четной подстроки
// с одинаковой суммой цифр слева и справа

using System;

  

class GFG {

  

static int findLength(String str)

{

    int n = str.Length;

    int maxlen = 0; // Инициализировать результат

  

    // Выберите начальную точку

    // каждой подстроки

    for (int i = 0; i < n; i++)

    {

        // Выберите конечную точку

        // четная подстрока

        for (int j = i + 1; j < n; j += 2)

        

            // Находим длину текущего субстрата

            int length = j - i + 1;

  

            // Рассчитать левую и правую суммы

            // для текущего субстрата

            int leftsum = 0, rightsum = 0;

            for (int k = 0; k < length/2; k++)

            {

                leftsum += (str[i + k] - '0');

                rightsum += (str[i + k + length/2] - '0');

            }

  

            // Обновить результат, если необходимо

            if (leftsum == rightsum && 

                maxlen < length)

                    maxlen = length;

        }

    }

    return maxlen;

}

  

  // Программа драйвера для проверки вышеуказанной функции

  public static void Main()

  {

    String str = "1538023";

    Console.Write("Length of the substring is " +

                                findLength(str));

  }

}

  
// Этот код создается нитином митталом

PHP

<?php
// Простая программа на основе PHP для определения длины
// самая длинная подстрока четной длины с той же суммой
// цифр слева и справа

  

function findLength($str)

{

    $n = strlen($str);

    $maxlen = 0; // Инициализировать результат

  

    // Выбрать начальную точку каждой подстроки

    for ($i = 0; $i < $n; $i++)

    {

        // Выберите конечную точку чётного

        // длина подстроки

        for ($j = $i + 1; $j < $n; $j += 2)

        {

            $length = $j - $i + 1; // Находим длину текущего субстрата

  

            // Рассчитать левую и правую суммы

            // для текущего субстрата

            $leftsum = 0;

            $rightsum = 0;

            for ($k = 0; $k < $length / 2; $k++)

            {

                $leftsum += ($str[$i + $k] - '0');

                $rightsum += ($str[$i + $k

                              $length / 2] - '0');

            }

  

            // Обновить результат, если необходимо

            if ($leftsum == $rightsum && 

                $maxlen < $length)

                    $maxlen = $length;

        }

    }

    return $maxlen;

}

  
// Код драйвера

$str = "1538023";

echo("Length of the substring is ");

echo(findLength($str));

  
// Этот код добавлен
// от Shivi_Aggarwal
?>


Выход:

Length of the substring is 4

Динамическое программирование [O (n 2 ) и O (n 2 ) дополнительное пространство]
Приведенное выше решение может быть оптимизировано для работы в O (n 2 ) с использованием динамического программирования . Идея состоит в том, чтобы создать 2D-таблицу, в которой хранятся суммы подстрок. Ниже приводится реализация подхода динамического программирования.

C ++

// Программа на C ++, которая использует Dynamic
// Программирование для определения длины
// самая длинная четная подстрока с той же суммой
// цифр в левой и правой половине
#include<bits/stdc++.h>

using namespace std;

  

int findLength(char *str)

{

    int n = strlen(str);

    int maxlen = 0; // Инициализировать результат

  

    // 2D таблица, где хранится sum [i] [j]

    // сумма цифр от str [i] до str [j].

    // Записи заполнены только

    // где j> = i

    int sum[n][n];

  

    // Заполняем диагональные значения для

    // подстроки длиной 1

    for (int i =0; i<n; i++)

        sum[i][i] = str[i]-'0';

  

    // Заполняем записи для подстрок

    // длина от 2 до n

    for (int len = 2; len <= n; len++)

    {

        // Выбрать i и j для текущей подстроки

        for (int i = 0; i < n - len + 1; i++)

        {

            int j = i + len - 1;

            int k = len / 2;

  

            // Вычисляем значение суммы [i] [j]

            sum[i][j] = sum[i][j - k] + 

                        sum[j - k + 1][j];

  

            // Обновить результат, если 'len' четное,

            // левая и правая суммы совпадают и

            // len больше чем maxlen

            if (len % 2 == 0 && 

                sum[i][j - k] == sum[(j - k + 1)][j] && 

                len > maxlen)

                maxlen = len;

        }

    }

    return maxlen;

}

  
// Код драйвера

int main(void)

{

    char str[] = "153803";

    cout << "Length of the substring is " 

         << findLength(str);

    return 0;

  
// Этот код добавлен
// Мукул Сингх.

С

// Программа на основе переменного тока, которая использует динамическое программирование для определения длины
// длинная четная подстрока с одинаковой суммой цифр в левой и правой половине
#include <stdio.h>
#include <string.h>

  

int findLength(char *str)

{

    int n = strlen(str);

    int maxlen = 0; // Инициализировать результат

  

    // 2D таблица, в которой sum [i] [j] хранит сумму цифр

    // из str [i] в str [j]. Только заполненные записи

    // записи где j> = i

    int sum[n][n];

  

    // Заполняем диагональные значения для солнечных лучей длины 1

    for (int i =0; i<n; i++)

        sum[i][i] = str[i]-'0';

  

    // Заполняем записи для подстрок длиной от 2 до n

    for (int len=2; len<=n; len++)

    {

        // Выбрать i и j для текущей подстроки

        for (int i=0; i<n-len+1; i++)

        {

            int j = i+len-1;

            int k = len/2;

  

            // Вычисляем значение суммы [i] [j]

            sum[i][j] = sum[i][j-k] + sum[j-k+1][j];

  

            // Обновляем результат, если 'len' четное, левое и правое

            // суммы одинаковы, а len больше, чем maxlen

            if (len%2 == 0 && sum[i][j-k] == sum[(j-k+1)][j]

                           && len > maxlen)

                 maxlen = len;

        }

    }

    return maxlen;

}

  
// Программа драйвера для проверки вышеуказанной функции

int main(void)

{

    char str[] = "153803";

    printf("Length of the substring is %d", findLength(str));

    return 0;

}

Джава

// Программа на Java, которая использует Dynamic
// Программирование, чтобы найти длину самого длинного
// четная подстрока с одинаковой суммой цифр
// в левой и правой половине

import java.io.*;

  

class GFG {

  

static int findLength(String str)

{

    int n = str.length();

    int maxlen = 0; // Инициализировать результат

  

    // 2D таблица, где хранится sum [i] [j]

    // сумма цифр от str [i] до str [j].

    // Записи заполнены только

    // где j> = i

    int sum[][] = new int[n][n];

  

    // Заполняем диагональные значения для

    // подстроки длиной 1

    for (int i = 0; i < n; i++)

        sum[i][i] = str.charAt(i) - '0';

  

    // Заполняем записи для подстрок

    // длина от 2 до n

    for (int len = 2; len <= n; len++)

    {

        // Выбрать i и j для текущей подстроки

        for (int i = 0; i < n - len + 1; i++)

        {

            int j = i + len - 1;

            int k = len/2;

  

            // Вычисляем значение суммы [i] [j]

            sum[i][j] = sum[i][j-k] +

                        sum[j-k+1][j];

  

            // Обновить результат, если 'len' четное,

            // левая и правая суммы одинаковы

            // и len больше чем maxlen

            if (len % 2 == 0 && sum[i][j-k] == 

                sum[(j-k+1)][j] && len > maxlen)

                maxlen = len;

        }

    }

    return maxlen;

}

  
// Программа драйвера для проверки вышеуказанной функции

public static void main(String[] args)

{

    String str = "153803";

    System.out.println("Length of the substring is "

                       + findLength(str));

}
}

  
// Этот код предоставлен Prerna Saini

python3

# Python3 код, который использует динамическое программирование
# найти длину самой длинной четной подстроки
# с одинаковой суммой цифр в левой и правой половине

  

def findLength(string): 

  

    n = len(string) 

    maxlen = 0 # Инициализировать результат

  

    # 2D таблица, в которой хранится sum [i] [j]

    # сумма цифр от str [i] до str [j].

    # Только заполненные записи являются записями

    # где j> = я

    Sum = [[0 for x in range(n)] 

              for y in range(n)]

  

    # Заполните диагональные значения для

    # подстроки длины 1

    for i in range(0, n): 

        Sum[i][i] = int(string[i]) 

  

    # Заполните записи для подстрок

    № длины от 2 до п

    for length in range(2, n + 1): 

      

        # Выберите i и j для текущей подстроки

        for i in range(0, n - length + 1): 

          

            j = i + length - 1

            k = length // 2

  

            # Рассчитать значение суммы [i] [j]

            Sum[i][j] = (Sum[i][j - k] + 

                         Sum[j - k + 1][j])

  

            # Обновить результат, если 'len' четное,

            # левая и правая суммы одинаковы и

            # len больше, чем maxlen

            if (length % 2 == 0 and 

                Sum[i][j - k] == Sum[(j - k + 1)][j] and 

                length > maxlen):

                maxlen = length

          

    return maxlen 

  
Код водителя

if __name__ == "__main__":

  

    string = "153803"

    print("Length of the substring is"

                    findLength(string)) 

      
# Этот код добавлен
# Ритурай Джайн

C #

// Программа на основе AC #, которая использует Dynamic
// Программирование, чтобы найти длину самого длинного
// четная подстрока с одинаковой суммой цифр
// в левой и правой половине

using System;

  

class GFG {

  

static int findLength(String str)

{

    int n = str.Length;

    int maxlen = 0; // Инициализировать результат

  

    // 2D таблица, где хранится sum [i] [j]

    // сумма цифр от str [i] до str [j].

    // Записи заполнены только

    // где j> = i

    int[,] sum = new int[n, n];

  

    // Заполняем диагональные значения для

    // подстроки длиной 1

    for (int i = 0; i < n; i++)

        sum[i, i] = str[i] - '0';

  

    // Заполняем записи для подстрок

    // длина от 2 до n

    for (int len = 2; len <= n; len++)

    {

        // Выбрать i и j для текущей подстроки

        for (int i = 0; i < n - len + 1; i++)

        {

            int j = i + len - 1;

            int k = len/2;

  

            // Вычисляем значение суммы [i] [j]

            sum[i, j] = sum[i, j-k] +

                        sum[j-k+1, j];

  

            // Обновить результат, если 'len' четное,

            // левая и правая суммы одинаковы

            // и len больше чем maxlen

            if (len % 2 == 0 && sum[i, j-k] == 

                sum[(j-k+1), j] && len > maxlen)

                maxlen = len;

        }

    }

    return maxlen;

}

  
// Программа драйвера для проверки вышеуказанной функции

public static void Main()

{

    String str = "153803";

    Console.WriteLine("Length of the substring is "

                    + findLength(str));

}
}

  
// Этот код добавлен
// Аканкша Рай (Abby_akku)

PHP

<?php
// Программа на основе PHP, которая использует Dynamic
// Программирование, чтобы найти длину самого длинного
// четная подстрока с одинаковой суммой цифр
// в левой и правой половине

  

function findLength($str)

{

    $n = strlen($str);

    $maxlen = 0; // Инициализировать результат

  

    // 2D таблица, в которой sum [i] [j] хранит сумму

    // цифр от str [i] до str [j]. Только

    // заполненные записи - это записи, где j> = i

  

    // Заполняем диагональные значения для

    // подстроки длиной 1

    for ($i = 0; $i < $n; $i++)

        $sum[$i][$i] = $str[$i] - '0';

  

    // Заполняем записи для подстрок

    // длина от 2 до n

    for ($len = 2; $len <= $n; $len++)

    {

        // Выбрать i и j для текущей подстроки

        for ($i = 0; $i < $n - $len + 1; $i++)

        {

            $j = $i + $len - 1;

            $k = $len / 2;

  

            // Вычисляем значение суммы [i] [j]

            $sum[$i][$j] = $sum[$i][$j - $k] + 

                           $sum[$j - $k + 1][$j];

  

            // Обновить результат, если 'len' четное,

            // левая и правая суммы совпадают и

            // len больше чем maxlen

            if ($len % 2 == 0 && 

                $sum[$i][$j - $k] == $sum[($j - $k + 1)][$j] && 

                $len > $maxlen)

                $maxlen = $len;

        }

    }

    return $maxlen;

}

  
// Код драйвера

$str = "153803";

echo("Length of the substring is "); 

echo(findLength($str));

  
// Этот код добавлен
// от Shivi_Aggarwal
?>


Выход:

Length of the substring is 4

Временная сложность вышеупомянутого решения составляет O (n 2 ), но требует O (n 2 ) дополнительного пространства.

[AO (n 2 ) и O (n) дополнительное пространство решения]
Идея состоит в том, чтобы использовать одномерный массив для хранения накопленной суммы.

C ++

// AO (n ^ 2) время и O (n) дополнительное пространство решение
#include<bits/stdc++.h>

using namespace std;

  

int findLength(string str, int n)

{

    int sum[n+1]; // Хранить накопленную сумму от первой цифры до цифры n

    sum[0] = 0;

  

    / * Сохранение накопленной суммы цифр от первой до последней цифры * /

    for (int i = 1; i <= n; i++)

        sum[i] = (sum[i-1] + str[i-1]  - '0'); / * конвертировать символы в int * /

  

    int ans = 0; // инициализировать результат

  

    / * рассмотреть все подстроки четной длины одну за другой * /

    for (int len = 2; len <= n; len += 2)

    {

        for (int i = 0; i <= n-len; i++)

        {

            int j = i + len - 1;

  

            / * Сумма первого и второго тайма совпадает с суммой обновления * /

            if (sum[i+len/2] - sum[i] == sum[i+len] - sum[i+len/2])

                ans = max(ans, len);

        }

    }

    return ans;

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    string str = "123123";

    cout << "Length of the substring is " << findLength(str, str.length());

    return 0;

}

Джава

// Java реализация O (n ^ 2) времени
// и O (n) решение дополнительного пространства

class GFG {

  

static int findLength(String str, int n)

{   

    // Хранить накопленную сумму из

    // Первая цифра в цифру n

    int sum[] = new int[ n + 1]; 

    sum[0] = 0;

  

    / * Хранить накопленную сумму цифр

    от первой до последней цифры * /

    for (int i = 1; i <= n; i++)

          

        / * конвертировать символы в int * /

        sum[i] = (sum[i-1] + str.charAt(i-1

                                    - '0'); 

  

    int ans = 0; // инициализировать результат

  

    / * учитывать все четные длины

    подстроки одна за другой * /

    for (int len = 2; len <= n; len += 2)

    {

        for (int i = 0; i <= n-len; i++)

        {

            int j = i + len - 1;

  

            / * Сумма первого и второго тайма

            это то же самое, что и обновление * /

            if (sum[i+len/2] - sum[i] == sum[i+len]

                                   - sum[i+len/2])

                ans = Math.max(ans, len);

        }

    }

    return ans;

}

  
// Программа драйвера для проверки вышеуказанной функции

public static void main(String[] args)

{

    String str = "123123";

    System.out.println("Length of the substring is " 

                    + findLength(str, str.length()));

}
}

  
// Этот код предоставлен Prerna Saini

python3

# AO (n ^ 2) время и O (n) дополнительно
# космическое решение в Python3

def findLength(string, n): 

      

    # Хранить накопленную сумму

    # от первой цифры до n-й цифры

    Sum = [0] * (n + 1

  

    # Хранить накопленную сумму цифр

    # от первой до последней цифры

    for i in range(1, n + 1): 

        Sum[i] = (Sum[i - 1] + 

              int(string[i - 1])) # конвертировать символы в int

  

    ans = 0 # инициализировать результат

  

    # учесть все четные длины

    # подстроки одна за другой

    for length in range(2, n + 1, 2): 

      

        for i in range(0, n - length + 1): 

          

            j = i + length - 1

  

            # Сумма первого и второго тайма

            # то же, что и обновление

            if (Sum[i + length // 2] - 

                Sum[i] == Sum[i + length] - 

                Sum[i + length // 2]):

                ans = max(ans, length) 

      

    return ans 

  
# Код драйвера

if __name__ == "__main__":

  

    string = "123123"

    print("Length of the substring is"

           findLength(string, len(string))) 

      
# Этот код добавлен
# Ритурай Джайн

C #

// C # реализация O (n ^ 2) времени и O (n)
// дополнительное пространство

using System;

  

class GFG {

  

    static int findLength(string str, int n)

    

          

        // Хранить накопленную сумму из

        // Первая цифра в цифру n

        int []sum = new int[ n + 1]; 

        sum[0] = 0;

      

        / * Хранить накопленную сумму цифр

        от первой до последней цифры * /

        for (int i = 1; i <= n; i++)

              

            / * конвертировать символы в int * /

            sum[i] = (sum[i-1] + str[i-1] 

                                   - '0'); 

      

        int ans = 0; // инициализировать результат

      

        / * учитывать все четные длины

        подстроки одна за другой * /

        for (int len = 2; len <= n; len += 2)

        {

            for (int i = 0; i <= n-len; i++)

            {

                // int j = i + len - 1;

      

                / * Сумма первого и второго тайма

                это то же самое, что и обновление * /

                if (sum[i+len/2] - sum[i] ==

                     sum[i+len] - sum[i+len/2])

                    ans = Math.Max(ans, len);

            }

        }

          

        return ans;

    }

      

    // Программа драйвера для проверки вышеуказанной функции

    public static void Main()

    {

        string str = "123123";

        Console.Write("Length of the substring"

        + " is " + findLength(str, str.Length));

    }

}

  
// Этот код предоставлен нитин митталь.

PHP

<?php
// AO (n ^ 2) время и O (n) дополнительное пространство решение

  

function findLength($str, $n)

{

    $sum[$n + 1] = array(); // Хранить накопленную сумму из

                            // Первая цифра в цифру n

    $sum[0] = 0;

  

    / * Хранить накопленную сумму цифр

    от первой до последней цифры * /

    for ($i = 1; $i <= $n; $i++)

        $sum[$i] = ($sum[$i - 1] +

                    $str[$i - 1] - '0'); / * конвертировать символы в int * /

  

    $ans = 0; // инициализировать результат

  

    / * учитывать все четные длины

    подстроки одна за другой * /

    for ($len = 2; $len <= $n; $len += 2)

    {

        for ($i = 0; $i <= $n - $len; $i++)

        {

            $j = $i + $len - 1;

  

            / * Сумма первого и второго тайма

            то же самое, что и обновление * /

            if ($sum[$i + $len / 2] - $sum[$i] == $sum[$i + $len] - 

                                                  $sum[$i + $len / 2])

                $ans = max($ans, $len);

        }

    }

    return $ans;

}

  
// Код драйвера

$str = "123123";

echo "Length of the substring is "

     findLength($str, strlen($str));

  
// Этот код добавлен
// Аканкша Рай
?>


Выход:

Length of the substring is 6

Спасибо Гаураву Ахирвару за то, что он предложил этот метод.

[AO (n 2 ) время и O (1) дополнительное пространство решение]
Идея состоит в том, чтобы рассмотреть все возможные средние точки (подстрок равной длины) и продолжать расширяться с обеих сторон, чтобы получить и обновить оптимальную длину, когда сумма двух сторон станет равной.

Ниже приведена реализация вышеуказанной идеи.

C ++

// AO (n ^ 2) время и O (1) дополнительное пространство решение
#include<bits/stdc++.h>

using namespace std;

  

int findLength(string str, int n)

{

    int ans = 0; // Инициализировать результат

  

    // Рассмотрим все возможные средние точки одну за другой

    for (int i = 0; i <= n-2; i++)

    {

        / * Для текущей средней точки 'i' продолжайте расширять подстроку на

           обе стороны, если сумма обеих сторон становится равной обновлению

           ans * /

        int l = i, r = i + 1;

  

        / * инициализировать левую и правую суммы * /

        int lsum = 0, rsum = 0;

  

        / * двигаться в обе стороны, пока индексы не выходят за пределы * /

        while (r < n && l >= 0)

        {

            lsum += str[l] - '0';

            rsum += str[r] - '0';

            if (lsum == rsum)

                ans = max(ans, r-l+1);

            l--;

            r++;

        }

    }

    return ans;

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    string str = "123123";

    cout << "Length of the substring is " << findLength(str, str.length());

    return 0;

}

Джава

// AO (n ^ 2) время и O (1) дополнительное пространство решение

  

class GFG {

  

    static int findLength(String str, int n) {

        int ans = 0; // Инициализировать результат

  

        // Рассмотрим все возможные средние точки одну за другой

        for (int i = 0; i <= n - 2; i++) {

            / * Для текущей средней точки 'i' продолжайте расширять подстроку на

           обе стороны, если сумма обеих сторон становится равной обновлению

           ans * /

            int l = i, r = i + 1;

  

            / * инициализировать левую и правую суммы * /

            int lsum = 0, rsum = 0;

  

            / * двигаться в обе стороны, пока индексы не выходят за пределы * /

            while (r < n && l >= 0) {

                lsum += str.charAt(l) - '0';

                rsum += str.charAt(r) - '0';

                if (lsum == rsum) {

                    ans = Math.max(ans, r - l + 1);

                }

                l--;

                r++;

            }

        }

        return ans;

    }

  
// Программа драйвера для проверки вышеуказанной функции

    static public void main(String[] args) {

        String str = "123123";

        System.out.println("Length of the substring is "

                + findLength(str, str.length()));

    }

}

  
// Этот код предоставлен Rajput-Ji

Python 3

# AO (n ^ 2) время и O (n) дополнительно
# космическое решение

def findLength(st, n): 

  

    # Хранить накопленную сумму из

    # от первой цифры до n-й цифры

    total = [0] * (n + 1

  

    # Хранить накопленное количество цифр

    # от первой до последней цифры

    for i in range(1, n + 1): 

          

        # конвертировать символы в int

        total[i] = (total[i - 1] + 

                   int(st[i - 1]) - int('0'))

  

    ans = 0 # инициализировать результат

  

    # учесть все четные длины

    # подстановок одна за другой

    l = 2

    while(l <= n):

  

        for i in range(n - l + 1):

      

            j = i + l - 1

  

            # итого первого и второго тайма

            # то же, что и обновление

            if (total[i + int(l / 2)] - 

                total[i] == total[i + l] -

                total[i + int(l / 2)]): 

                ans = max(ans, l) 

        l = l + 2

      

    return ans 

  
Код водителя

st = "123123"

print("Length of the substring is"

           findLength(st, len(st)))

  
# Этот код предоставлен ash264

C #

      
// AO (n ^ 2) время и O (1) дополнительное пространство решение

using System;

public class GFG {

   

    static int findLength(String str, int n) {

        int ans = 0; // Инициализировать результат

   

        // Рассмотрим все возможные средние точки одну за другой

        for (int i = 0; i <= n - 2; i++) {

            / * Для текущей средней точки 'i' продолжайте расширять подстроку на

           обе стороны, если сумма обеих сторон становится равной обновлению

           ans * /

            int l = i, r = i + 1;

   

            / * инициализировать левую и правую суммы * /

            int lsum = 0, rsum = 0;

   

            / * двигаться в обе стороны, пока индексы не выходят за пределы * /

            while (r < n && l >= 0) {

                lsum += str[l] - '0';

                rsum += str[r] - '0';

                if (lsum == rsum) {

                    ans = Math.Max(ans, r - l + 1);

                }

                l--;

                r++;

            }

        }

        return ans;

    }

   
// Программа драйвера для проверки вышеуказанной функции

    static public void Main() {

        String str = "123123";

        Console.Write("Length of the substring is "

                + findLength(str, str.Length));

    }

}

   
// Этот код предоставлен Rajput-Ji

PHP

<?php 
// AO (n ^ 2) время и O (1) дополнительное пространство решение

  

function findLength($str, $n)

{

    $ans = 0; // Инициализировать результат

  

    // Рассмотрим все возможные средние точки одну за другой

    for ($i = 0; $i <= $n - 2; $i++)

    {

        / * Для текущей средней точки 'i',

        продолжайте расширять подстроку на

        обе стороны, если сумма обоих

        Стороны становятся равными обновления

        ans * /

        $l = $i;

        $r = $i + 1;

  

        / * инициализировать левую и правую суммы * /

        $lsum = 0;

        $rsum = 0;

  

        / * двигаться с обеих сторон до

        индексы выходят за пределы * /

        while ($r < $n && $l >= 0)

        {

            $lsum += $str[$l] - '0';

            $rsum += $str[$r] - '0';

            if ($lsum == $rsum)

                $ans = max($ans, $r - $l + 1);

            $l--;

            $r++;

        }

    }

    return $ans;

}

  
// Программа драйвера для проверки вышеуказанной функции

  

$str = "123123";

echo "Length of the substring is " .

        findLength($str, strlen($str));

return 0;

  
// Этот код предоставлен Ita_c.
?>


Выход:

Length of the substring is 6

Спасибо Гаураву Ахирвару за то, что он предложил этот метод.

Эта статья предоставлена Ashish Bansal . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Самая длинная четная подстрока, так что сумма первой и второй половины одинакова

0.00 (0%) 0 votes